Hard to imagine something external messing up malloc(), I would suspect linux is the key difference here. Are you using a script to start arduino (run.sh or something)? I know strange things can happen in windows if you do not use the script, there is less possibility of linking in the wrong malloc on windows too
I tried 0010 and 0011 fyi, on a lot of chips. Some that I had used the IDE to load the decimillia bootloader on too.
FYI, in addition to the supercheap but flakey parallel iCSP, there is also a bit of code to turn a duino into an icsp programmer if you want to try a different bootloader:
http://www.arduino.cc/playground/Code/Programmer2