I was able to recreate an issue where after sending bitcoins and then restoring the wallet the transaction never shows any confirmations even though the transaction did make it to the recipient and does appear in BlockExplorer.

The steps I performed were:
1.) Create a new wallet
2.) Requested a new address
3.) Received some seed bitcoins (two transactions) to that new address.
4.) Made an archive of my wallet.
5.) Sent two test payment transactions. (to 16W7FAZ8tcX1gDLgDupfAKfpGLYd7XcPRe a 0.02 BTC and a 0.03 BTC)
6.) Recover wallet from archive.

After many blocks passed (more than an hour), the confirmations still shows 0/unconfirmed. To confirm that the payment was sent, I confirmed:
http://blockexplorer.com/address/16W7FAZ8tcX1gDLgDupfAKfpGLYd7XcPRe

To try to get a clean load of blocks, I then purged the blk*.dat, __db*, addr.dat, .log and database/ (i.e., all files except wallet.dat) and started bitcoin again.
$ bitcoin -datadir=.

After letting the client catch up to the most recent block, ... and then waiting at least an hour further, my two test transactions still show 0/unconfirmed.

The test wallet (with 0 BTC balance) that can be used to recreate this issue is at:
http://c1958612.cdn.cloudfiles.rackspacecloud.com/wallet.dat