Well, WA tries loading the replay with the EXE stored in the Registry. Therefore if you have 3.6.28.0 saved in your registry (I think that's the version provided in NE), it's that EXE that will try loading the replay, even if you do have a newer version somewhere on your HDD.
To change your associations to 3.6.31.0: run it, go to the Options > Advanced Options menu, enable "Auto-register associations", save changes and quit the game. Relaunch it with Admin rights and you should be set; you'd then be better off restarting the game once more and without Admin rights, as they're known to cause problems. I'd recommend you to update to 3.7.2.1 and follow those steps on that version instead though, unless you have a valid reason not to use 3.7.2.1. Among other things, you'll be able to watch 3.7.x.x TUS replays just fine with it.