It may just be my client. I'm using 1.4, it could also be a timing issue.

Tranactions are created with other inputs, if you have to many inputs making up the transaction it can become to large.
Its is an issue that affects ALL wallets, and is worse if you have lost of tiny transactions or mined blocks
You can fix this by "dusting" or "defragmenting" your wallet.
1. Backup old wallet.dat and move to a safe location
2. start wallet so you get a new wallet.dat, record the address
3. swap the old wallet back and send all your coins to the new address (you may have to do a bunch of small transactions)
4. once you have moved all the coins to the new wallet, you can send them back to the original wallet in one transaction.
Now you wallet will just have one input to build transactions from
