I restored my wallet again, and it has downloaded the chain up to the most recent block again.
If for some reason the transaction hadn't been announced to the network and you then restored your wallet from a backup, then the network never knew you made that transaction, and now your local client doesn't either.
But there's no guarantee that the earlier transaction didn't make it to a node. That transaction could be queued as could still could go through.
Normally, the bitcoin client will attempt to re-announce the transaction at a later time. But you need to leave the client running -- for an hour or longer even, perhaps, for it to finally retry sending the transaction out. But now that you've restored the wallet, the client won't be retrying anything.
You can always check to see a queue that helps to determine if a transaction has been announced to the network. The queue shows transactions that were announced but are not yet included in a block.
And once it is in a block, it will appear in Block Explorer:
After 6 confirmations, the client will change from unconfirmed to confirmed.
So, if your wallet doesn't know about that transaction, and it isn't showing as a queued transaction nor appears in block explorer, then you probably are safe in assuming the transaction never made it out.