First of all, are you now, or were you ever, running a modified client that messed with the required minimum transaction fees?  If so, there's your problem.

If not, then your problem is that you have an unconfirmed transaction that the network no longer sees, and that will thus never be confirmed, tying up your coins in your wallet indefinitely.  You need to remove that transaction from your wallet file.  I don't specifically know how to accomplish this, but as the wallet file is just unencrypted binary data, and the client that reads and writes the wallet file is entirely open source, it is definitely possible.  Somewhere out there should be a wallet munger program that lets you import/export private keys, modify transactions, etc.  Obviously make a wallet backup before trying anything like that.