Since you confirmed that /usr/bin/chsh is setuid root (and therefore should allow non-privileged users to change their own login shell), the most likely explanation for this behavior is that either
- your current login shell was not in the /etc/shells file
or
- your current login shell was restricted (most likely
/bin/rbash)
Ex.
$ grep fish /etc/shells || echo "invalid shell"
invalid shell
$
$ sudo chsh -s /usr/bin/fish testuser
$
$ su - testuser
Password:
Welcome to fish, the friendly interactive shell
testuser@t400s ~> chsh -s /bin/bash
You may not change the shell for 'testuser'.
testuser@t400s ~> exit
Note that there is no restriction on root setting a user's login shell to an invalid shell (as here), and doing so does not make an invalid shell valid by adding it to the /etc/shells file.
$ sudo chsh -s /bin/rbash testuser
$
$ su - testuser
Password:
testuser@t400s:~$
testuser@t400s:~$ chsh
You may not change the shell for 'testuser'.
testuser@t400s:~$ exit
If the target shell was absent from the /etc/shells file, you would have received a different message:
$ sudo chsh -s /bin/bash testuser
$
$ su - testuser
Password:
testuser@t400s:~$ chsh -s /usr/bin/fish
Password:
chsh: /usr/bin/fish is an invalid shell