Not achieving 100% speed on vertical games does not necessarily mean your card is struggling. Check
this.I wouldn't bother upgrading. In Linux, the compatibility gap between HD 4xxx and HD 5xxx is not as drastic as in Windows. Both work reasonably well. You'll get gradual benefits by upgrading, but only for higher work loads like running super resolutions, etc. Super resolutions are not so relevant in Linux anyway.
Anyway, if you had no card at all and you were to buy a new one, it would be absurd to get an HD 4xxx today, whatever your OS was, unless you wanted to run Windows XP.