Why does the output from my script say "mv: command not found" but not when I run it on the shell directly?

It probably is a matter of PATH setting. The /bin directory should be inside your $PATH

For debugging purposes, add

echo PATH is $PATH

at start of your script, and perhaps put #!/bin/bash -vx as your script's first line. See this, execve(2), bash(1).

As a workaround, replace

         mv "$i" "$new"

with

         /bin/mv "$i" "$new"

CodeHunter