You're not up against MySQL's limitations, you are battling bad server setup.
MySQL requires at least 2mByte per connection, but you have only 512MB.
512MB/1000=500kBbyte per process that's only a quarter of the bare minimum.
Your spends all it's time swapping to disk, which means queries take a lot longer, which means the MySQL connections are in use for way too long, which looks like you are short on connections. But increasing the number of connections only makes the problem worse.
I suggest you start by adding 1000*2MB=2GByte of memory for the connections, and about 1GByte for cache, make it an even 4GByte total (to give the OS and Filesystem some space)
While you're spending money, I'd also recommend getting a SCSI or IDE RAID array to speed up disk-access.