Character encoding problem with decryption in PHP from C#

I think I've got a good one for you.

I've got some C# code that encrypts and decrypts strings. It looks something like this :

    public static string EncryptString(String toEncrypt, String key)
    {
        Debug.WriteLine("Encrypting string: " + toEncrypt + "&key:" + key);
        Rijndael AES = Rijndael.Create();
        AES.KeySize = 128;
        AES.BlockSize = 128;
        AES.Mode = CipherMode.ECB;
        AES.Padding = PaddingMode.Zeros;
        MD5CryptoServiceProvider Hasher = new MD5CryptoServiceProvider();
        AES.Key = Hasher.ComputeHash(UTF8Encoding.UTF8.GetBytes(key));
        ICryptoTransform crypto = AES.CreateEncryptor(AES.Key, AES.IV); 
        byte[] txt = UTF8Encoding.UTF8.GetBytes( HEADER + toEncrypt);
        byte[] cipherText = crypto.TransformFinalBlock(txt, 0, txt.Length);
        return Convert.ToBase64String(cipherText);;
    }

When I encrypt or decrypt in C# it works like a charm. In php I have a decryption algorithm that looks like this:

    if($msg!= "" && $key != "")
    {           
        $msg = parseMsg($msg);
        mcrypt_get_key_size ( MCRYPT_RIJNDAEL_128,  MCRYPT_MODE_ECB);
        $decrypted = mcrypt_decrypt(MCRYPT_RIJNDAEL_128, md5($key,true), base64_decode($msg),MCRYPT_MODE_ECB);      
        $headerLoc = strpos($decrypted,$correctHeader);         
        /*$decrypted = str_replace($correctHeader,"",$decrypted);
        for($x = 0; $x < 31; $x++)
        { 
            // an attempt at getting rid of control characters
            $decrypted = str_replace(chr($x),"",$decrypted);
        }*/
    }

The commented out code is just some of the attempts I've made to get the string decoded correctly. The strange part, is that sometimes it works and sometimes it doesn't even without 开发者_StackOverflowstrange characters.

For example:

Herp Derp with key: Red works

Message Herp Derp with key swordfish does not work.

Long messages with the key red do no work.

No message with key swordfish works.

Could that mean that the length of the message key is part of the problem?

I have ensured that the message and the key are correctly transmitted between the php and the C# it is definitely a problem with the encoding/decoding, and based on the garbage that's spit out I think it has to do with UTF8 encoding. I suspect the padding mode as a possible culprit as well, any ideas? Edit: I didn't notice the 1 or 2 missing pluses that would foobar the whole string, Sorry Stack :\ *

Does anyone know how to fix it?

Edit After changing to key size, no strings work. With message Herp Derp and password red, php outputs decrypted as .�ʇ'y-�US2~h\�0�nAZ=�\2/�����|�a���R�`�/������nY�<[B�NB�