I have a 2007 Mac Pro (running Lion) that has been on the same schedule for a long time; it is set to go to sleep at 1am, and wake up at 7am. Recently, it sleeps through its wakeup time. If I press any key or anything, it wakes up immediately - and I notice the clock is off (it quickly corrects itself). It is as if when it is asleep, it is no longer keeping time, and doesn't know when to wake up. Could this be a dead button-battery inside? I thought these were only used if no AC power was present (it always has power).
Try resetting the System Management Unit (SMU); the SMU is typically responsible for tracking when your Mac is scheduled to wake up.
With regard to your Mac Pro appearing not to keep time, this is not a problem. It is expected behaviour for the menu bar clock to update a few seconds after your Mac has woken up.
The process controlling the clock needs to get a change in time notification before updating; it will not match your Mac's internal clock immediately upon waking up.