However, I also sent recently about 12.7 bitcoins to GLBSE and that payment is now stuck in "unverified hell". I tried repeating the above steps but when I redownloaded the block chain my bitcoins did not come back. What can I do to recover this payment? Can I pay someone to process my transaction? Can I revoke it? If it's just sitting there unverified there must be some way to get it processed, right? [edit: payment was sent on the 21st.] Thanks.
If this transaction never made it into the network at all, you can use pywallet to delete it. Otherwise, if you wait, eventually -- if the wallet is connected to the network -- it'll rebroadcast and propagate.
Can you find the transaction here: http://bitcoincharts.com/bitcoin/txlist/
(edited for a better unconfirmed transaction locator)