Bueno, ya esta solucionado el problema :D , para ello he hecho uso de imap_mime_header_decode.
Código PHP:
$subject = imap_mime_header_decode( $msg_info->Subject );
for($i = 0; $i < count($subject); $i++) {
$tema .= $subject[$i]->text;
}
Espero que a alguien le ayude :D