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.