Image/Media Uploader in MarsEdit (offline blog editor) works fine, whereas the web based interface throws-up the HTTP error.
(While the mod_security workaround solves my problem with the web based interface, I am not sure I want to do that.)
Thought I'd share this with people having similar problems. The point: Try offline blog editor and it uploads your image, crunches it to sizes you've set in Settings > Miscellaneous, and uploads the image/media to relevant folder---per your WordPress settings.