Found the answer, in case someone might have same problem:
I found that I have 2 convert commands in my server. First one is in /usr/bin version 6.0, second one is in /usr/local/bin version 6.3
PHP sees the first, the bugged one, and linux sees the second one...
When I entered the path to the exec command, problem is solved
exec("/usr/local/bin/convert -size 320x85 xc:transparent.........");