the last version of titanium backup is able to totally remove system and/or preinstalled apps, like amazonmp3 etc. tried it and it worked for me, after two reboots the app is completely gone!
all of the above "hacks" didn't work for me (although i am temp rooted with visionary and used the "su" command), but titanium backup did the trick!
click and hold on the app, choose "force remove app (by recovery exploit)"
Samsung G-Tab 7.7-16 & G-Note II-16
Samsung G-Note-32 (retired)
Samsung G-Tab 10.1-16 (sold)
Samsung G-SII-16 (sold)
HTC Desire HD (sold)
HTC HD2 (retired)
HTC Diamond (retired)
HTC Trinity (sold)
FSC Pocket Loox n560 (retired)