Odd, since PHP Info is listing “bundled (2.0.28 compatible)”. At this point I would recommend contacting your server admin, as it appears that the GD 2 lib is not installed properly or working as it should be. Same with ImageMagick - if it’s installed properly and you have added the server path to ImageMagick in the Image Resizing Prefs, it should have worked like a charm.
Did you get any errors when you tried it with ImageMagick? And is display_errors enabled (check PHP Info) and your output and debugging preferences in ExpressionEngine set to display errors to Super Admins?