Sounds like the same problems as me.
The Big Empty wasn't too bad with the lagging for me, but in later levels, like 2-11, Ghost Key, the game completely locks up with the lag. In that level, the lag begins as soon as I touch the wall of locks in front of you at the start; not the floor, the floor's fine, (right up until it disappears, anyways :p), but just touching the wall of locks sends my processor churning, and the next couple of frames are usually impossible ones; Ie: meatboy dying behind the wall of locks, or on the wall of locks.
Secondly, I noted that although the first bandage character did not unlock, the second one did, when I got 30 bandages, and while I was able to select him when entering a level, the character select in-level did not work properly.
Also on the X86 version.
Did you ever find a solution to your problem? I've tried different resolutions, fullscreen, med/low/ultralow detail, (from the command line: -meddetail -lowdetail, -ultralowdetail), but the lag isn't caused by graphics.
edit: Er . . . to reduce the lag issues, turning the sound effects down to 0 works.
The bug tracker for linux is here:https://bugzilla.icculus.org/buglist.cgi?quicksearch=super+meat+boy
And this particular problem is here, with said quickfix:https://bugzilla.icculus.org/show_bug.cgi?id=5348