I had also stuck coins (however produced by my own fault when I experimented with the code a little). The problem is that your wallet still stores the transactions, even if no other node remembers them anymore -- at least in my case it was like that, because the transaction was not forwarded properly any more by other clients; I haven't checked whether that's also the case for you.
I got the coins finally free again by creating a fresh wallet and importing the private keys to all addresses that had coins on them from the old wallet. This can be done with the "dumpprivkey" and "importprivkey" commands of bitcoind (I'm not familiar with any GUI clients). See also
https://en.bitcoin.it/wiki/How_to_import_private_keys_v7%2B.
