By the way, by far the most common support request I have at my pool is
users withdrawing coins and not seeing it in their wallet because it's
not up-to-date with the block chain. Might be worth adding something in
the bitcoin-qt GUI to make it more obvious that users can't see new
transactions and why.

For 0.7 we've added a red "(out of sync)" warning to the balances when the block chain is out of date.

However, due to the design of the protocol there is a large variance in block timings, and it is not possible to determine up-to-date status with certainty, so quite a large safety margin is used. To be precise the warning is shown when the last received block was generated more than 90 minutes ago.

Wladimir