I have a similar issue, and I don't think it is a transaction complexity problem. I have an address with a single transaction that I cannot send coins from.
In my case, I have a block reward from solo mining that caused my Bitcoin client to crash in May, when I first tried to spend it. Shortly afterward, the client would crash or close every time it tried to open the wallet. I used pywallet to extract the private keys for that address and other addresses with coins. I was successful in importing the private keys and spending coins from all other addresses.
Here's what is strange. If I import the private key in a unencrypted wallet, the Bitcoin client crashes when it tries to open the wallet. If I import the private key in an encrypted wallet, the Bitcoin client shows the 50.xxx coins in the wallet. However, if I try to send them, I get "Transaction creation failed". I have also tried several releases (from 0.3x to 0.7RC1) with no luck.
I've heard there is an issue with some addresses created on earlier clients and encrypted with newer client releases. I didn't hear back from Gavin (he's excused if he's been busy

) I think I'll ping him again to clarify if there is a known issue.
Did I read somewhere that mtgox will let you import private keys? You could try that, see if that works... or you crash them.