If any CPU-overcommitted VM system has guests which all want 100% of the CPU, they'll all suffer. No two ways about that. I don't know what hardware Linode put their 512MB instances on, and I don't know their overcommit ratio. 128 is more guests than I'd put on a 64GB host, though.

If your typical load is actually at 100% CPU for the majority of the time, I'll go out on a limb and suggest that VPS might not be the best bet anyway.