Testing your request with the facebook APIs APIs worked great for me. You can try to add an additional parameter "image" in your post and put a link to your image in it.
So facebook is forced to use this as an image in a post.
$result = $facebook->api( '/me/feed/', 'post', array('access_token' => $token, 'message' => str_replace($link,'',$msg), 'link' => $link, 'picture' => 'http://images.ephotozine.com/gallery/2011/49/normal/52194_1323334048.jpg') );
source share