Digging some more revealed that the imagecreatefromstring was not the source of failure.
Strange Base64 encode/decode problem
seems like the encoding removes the + characters and replaces them with space instead.
Solution to my problem so far is:
str_replace(' ','+',$image);
and then afterwards do the base64_decode.
Should anybody have a better solution, please let me know..