That was included in the "I have tried everything" category.
If you had 'tried everything' you wouldn't be posting up a thread. Wow a freaking step by step after 10 seconds of searching. GO BACK TO WINDOWS.
To enable playback of .wmv and some other filetypes through Totem, follow these steps:
1. Add gstreamer0.8-ffmpeg and gstreamer0.8-pitfdll packages from Universe branch of repository
2. Download "Windows all" codecs package from mplayerhq.hu
3. Put all files from this package to /usr/lib/win32 (I mean really FILES, not the folder that is inside the archive)
NOTE: This will not guarantee the smooth playback of "absolutely any" wmv-file. It will Just allow GStreamer to load windows .dll's to decode the video stream.
Unfortunately, gstreamer0.8-pitfdll is only available for i386 and not the AMD64 version of Ubuntu.