I just had exactly the same problem. I tried sending another mail and it worked, but the first mail kept giving this message.
So I quit Mail, then started it again, and the message was sent fine.
Silly Mail.
I was running OS X 10.4.11 with lots of free disk space. Before quitting mail I checked the permissions on the Outbox folders and everything looked OK to me. Simple Mail bug it looks like.