You could try to see if convert need some library's that you don't have on the system.
If you don't have correct library you could see that the arrow that point to the correct file says something about file missing.
Execute this command to list the application's needed library's:
ldd $(which convert)
Something like this as result(this is small of my result):
libc.so.6 => /usr/lib/libc.so.6 (0x00007f436bad9000)
liblcms2.so.2 => /usr/lib/liblcms2.so.2 (0x00007f436ba73000)
libraqm.so.0 => /usr/lib/libraqm.so.0 (0x00007f436ba6b000)
liblqr-1.so.0 => /usr/lib/liblqr-1.so.0 (0x00007f436ba5b000)
libxml2.so.2 => /usr/lib/libxml2.so.2 (0x00007f436b8cf000)
libfontconfig.so.1 => /usr/lib/libfontconfig.so.1 (0x00007f436b87f000)
libfreetype.so.6 => /usr/lib/libfreetype.so.6 (0x00007f436b7b4000)
And if ImageMagic don't works, you could try ffmpeg, to do transpose a image.
Like this:
ffmpeg -y -i 'sample.jpg' -vf transpose=2 'out.jpg'