Puzzling. It should work. I've resized loads of images that are even bigger, and ImageMagick does this better and faster than most other software. I don't remember exactly, but i think my code does something like:
convert -size 250x400 blabla.jpg -geometry 3300x2500