That's all nice and interesting, but:
You didn't show us what your PATH looks like.
e.g. a PATH of:
PATH=/foo:/bar~bin:/baz
wouldn't be of much use to execute stuff in ~/bin.
You also didn't show us the permissions on your script - you
mention: "executable", and "owned by me", but you don't specify by
what manner it is "executable" - is that permissions, or the data
content? There can also possibly be permissions issues with
directory or parent directories up the physical path.
Also, depending upon what happened and what order, and one's shell,
one might need to issue the "rehash" command or similar. If you fire
off a fresh shell, and that doesn't have the issue, that could be one
indicator that that may be the issue.