I'm a huge fan of Couch to 5K as a training program for running. (http://www.coolrunning.com/engine/2/2_3/181.shtml) Even though you have base, it is important to go slow when you start running so your muscles and joints can adapt to the pounding. I always *hated* running, but then did couch to 5K and really enjoy it now.

Good luck!