Linux is UNIX in the context of my question. On Linux the shebang is actually handled by the kernel. When you load a binary and attempt to execute it with a syscall, the kernel reads the first few bytes of the binary. If it is an ELF header, it executes the machine code as you would expect. If the first two bytes are "#!", then it interprets it as a shebang header and loads the specified binary to interpret it.

Again, this is kernel code. I admit I'm a bit confused as to why it didn't work on your system. This shouldn't be handled at the shell level.