It looks like you have run into the same fundamental problem I am trying to address before I can implement rollntime.

Essentially the server is rejecting your work because it is too old, not because kernel processing took too long. At 65 Mhash/sec, it will take just over a minute to process an entire WorkUnit of 2^32 nonces. Now, this work is not necessarily "stale" because it's from the current block and it meets the target specified by the server. This is made worse by the fact that Phoenix maintains a second WorkUnit in the queue by default. On a 5870 that can check the entire 2^32 space in 10-11 seconds, this is beneficial because it allows the miner to continue running during momentary connection disruptions or server load spikes. However, on hardware that takes over a minute to process 2^32 nonces, this can cause shares to be submitted from WorkUnits that are over 2 minutes old. This won't cause problems when the block changes because all work from previous block will be discarded immediately.

Rollntime introduces the same problems, since even very fast miners can now function for 30-60+ seconds on a single WorkUnit. The queue behavior needs to be adjusted to account for this. Most likely the solution will involve monitoring how much time is left until the miner runs out of work, and fetching more work when it falls below some value.

The message you are getting is sent by the pool server using x-reject-reason. I'm going to guess that the pool you are connecting to "forgets" about work it has assigned after some amount of time. (probably to save resources) I recommend trying other pools to see if you get the same behavior.

That said, aggression 12 on hardware doing only 65 Mhash/sec is probably not a good idea. Your kernel execution times are going to be something like ~4 seconds. This is problematic because you can't reasonably interrupt kernel executions to switch work. (eg: when the block changes) On average this is going to mean 2 seconds of wasted time per block (which amounts to a 0.33% loss) Try aggression 10 or so, which should limit this effect without much of a hashrate drop.

You can also use -q 0 to disable the queue entirely. This cuts your work age in half compared to the default of 1, but you might see the miner idling once per minute when it needs new work. At aggression 10 (kernel execution time 1 second) this shouldn't be a problem under normal cases. This allows for enough time to fetch new work before the miner runs out completely. However, this doesn't work at low aggression where the kernel execution time is a small fraction of a second.