I was under the impression you could send any size transaction with any size fee or no fee, and it would depend on which miner processes the next block whether it would be confirmed in that block or not. (And that if the next miner didn't accept it, it would then have a chance of being confirmed in the next block, and so on.)
That assumption is true. It is up to miners to integrate any transactions they wish to the blocks they're attempting to solve. I think that warning is an implemented (but not enforced) guideline about transaction fees in the standard client. He can still try to submit the tx for free, and chances are one of the miners that integrate tx regardless of fee will take care of it(~99% of the network right now).
What this warning shows is how much you'd be expected to "tip" in order to have that tx processed in the late future.
Also, the message gets me thinking the guy is using a 0.005 BTC/kb fee client and that his tx is actually 1,180kb wide, which is why the client is bitching about "size limit", which is currenctly capped at 1mb per block.