Authentication: MD5 to SCRAM-SHA-256 error

Hello,
We're currently using PostgreSQL version 10.5 in a Linux environment. We
were wanting to change the password authentication from MD5 to
SCRAM-SHA-256. I performed these steps to do so:
1) Modified the postgresql.conf and changed the password_encryption entry
from "md5" to "scram-sha-256".
2) restarted the database
3) Changed all our users password to a default password using the command:
alter user xxx password 'xxx';
4) Once I did this, I could run this sql statement and verify the password
was now a sha-256 password:
select passwd from pg_shadow where username = 'xxx'
5) Finally, i went into the pg_hba.conf file and changed the
authentication method from md5 over to scram-sha-256.
6) restarted the database again.

However when I try to log in now, via command line, I receive the error:
"psql: authentication method 10 not supported". I tried to search online
for this error but everything I've seen implies that occurs when some
client's libraries are not compatible, but i'm just using psql via the
command line.

What's worse...I tried to set everything back to MD5 and i'm still getting
the exact same error. Has anyone else experienced this? The only thing I
can think of is that even though I'm on version 10.5, maybe somehow I have
old libraries it's trying to use to connect?

Any help would be greatly appreciated!
Thanks!