Ctrl M Weirdness

[LittleLinuxGuy]

Here's the top of my python script:
#!/usr/bin/python

OK, so far.
On the command line, I get a #!/use/bin/python^M error.

Oh, OK, I fire up vi and type -
:%s/ctrl-v ctrl-M//g
to get rid of the ctrl 'M's - I did write the file on a Windows box but I set my editor to save the files as UNIX type It's PSpad editor by the way. I haven't had this problem with any other python script.

And I get a "pattern not found" message from vi. ?!?!?!

I try re-running the script at the command line, same thing.
I brought the script up in emacs to see if it sees the ^M - nope!

I tried deleting that line in vi and retyping it - Nope.

I'm on Fedora 7

It's driving me batty!

Help! Any suggestions would be really appreciated!
I really don't want to have to retype the sucker in vi!