I do a 2 mile, high intensity, 40 min program on a treadmill with varied speeds/inclines, usually every other day. Honestly I think the class alone is a great cardio workout in itself, I'm running for different reasons. If your lifting and doing cardio make sure you eat a ton of food (depending on your metabolism). Your protein/carb requirements are key to keeping your results.
The decrease in strength you noticed, how long have you noticed it? Some people just have off days were they are drained.
Keep in mind i'm no expert Im just been learning as I go, I read that fighters in thailand run every morning for about 2 miles, so I based my program off that. However I too was worried I would lose my lifting results so I added in some rest time, and increased my food intake. From my breif session with a personal trainer you do not wanna run a day before or after an intense leg workout, as the muscles need time to grow. Hope that helps.