sudo -u fails with env: -u: No such file or directory

Turns out sudo was actually running an alias:

$ alias sudo
alias sudo='sudo env PATH=$PATH'

Running /usr/bin/sudo directly skipped the alias and resolved the problem.

Alternatively, you can open the .bashrc file in your home directory and comment out the line:

alias sudo='sudo env PATH=$PATH'

Run source .bashrc again, and (for good measure), run unalias sudo.