Check out the Celebrity Fitness Check-in thread
There are some great workouts for starting over. Claudia Schiffer, Elle MacPherson, Cindy Crawford, & Jane Fonda all have good workouts that are safe, effective and not too easy. For strength, I think Claudia has perfect overall workouts for those getting back into exercise.
Ellen Barrett's streaming site has some nice workouts, too.