Well I have some questions for some of the experianced. First off I was in the army in 2000 and got a med 40 discharge for stress fractures. Before I enlisted I was actually in the DEP with a SEAL Challenge contract. I then got worried about not being able to make it. Then the excuse was my girlfriend (Whom I have been married to for 6 years now.) but with what I know now I don't think that I was mature enough. Back to the topic, would I be able to reenlist in the Navy and hopefully be awarded the chance at BUD/S? Also for someone who is out of shape and starting from complete scatch where should I start out workout wise?

Physically I was in your exact position 5 months ago, COMPLETELY OUT OF SHAPE.
The two biggest pieces of advice I recommend is to first start with www.crossfit.com, the workouts may look intimidating but every workout is scale-able, that is where I started for my workouts.

Second, the other biggest thing that helped me physically would the Naval Special Warfare Training Guide. It is a 6 month training guide, I use this guide specifically for my running and swimming (not the calisthenic workouts, they are lacking)
This guide can be found here
http://thesealquest.infopop.cc/eve/forums/a/tpc/f/335109136/m/6531014032/p/2

When I started getting back into shape I was 235lbs. and could barely finish a 1.5 mile run, I have since lost 35lbs. and can routinely run more than 5 1/2 miles at one time, twice a week with ease.

Both programs work, they have for me.

stay focused.

-Blake-

A good place to start as well is:

http://www.sealswcc.com

and

http://navyseals.com/crossfit-workout-day

Stay tuned for the TSQ Workout Charts as well. It is something we are working on.

Plus you should try and challenge yourself here:

http://sealstrongnation.com/