Error messages are only a glimpse and usually a misguiding one, obviously the codec exists since like I said it plays in WMP.
 
This is an existing MediaElement issue, have seen it on both win32 and win64 machines. Video would reliably load in WMP yet MediaElement would sometimes fail. Tried different codec packs and maybe a driver update and don't see this anymore.

Another issue is if your WPF process is native 64 bit, here it will always fail except for maybe the basic wmv and mpg, most directshow filters run in 32bit only I suppose.