That ^M is a dead giveaway - it looks like the script has Mac line-endings (Ctrl-M) instead of Unix line-endings (Ctrl-J).
It won't appear as a literal ^M - in fact depending on your text editor it might not be shown at all.
You don't say which operating system you have, so I'm not sure which tools you have on your system but could you try to get a character (not hex) dump with:
od -tc newshit.sh
...and tell us whether the /bin/sh is followed by \r, \n or \r\n ?
I'm expecting you'll see something like:
0000000 # ! / b i n / s h \r
Or if you run:
cat -e newshit.sh
...that will display the carriage return character if it's there.