MariaDB 10.5 refusing remote connections

I've gone through a lot of tutorials and questions and I still can't get it to work.

I installed MariaDB 10.5 on a Debian 11 server. We changed its IP address yesterday and since then we cannot do a remote connection. The database answers "Access Denied to user@host on database"

We created some users to test:

GRANT ALL PRIVILEGES ON db.* TO 'user'@'host.domain.com' IDENTIFIED BY 'something';

Does local connections work?

Yes, as we granted the privileges to localhost access.

Did you verify the users were added correctly?

I think so:

MariaDB [(none)]> SELECT User, Host FROM mysql.user WHERE Host <> 'localhost';

+--------------+------------------------+
| User         | Host                   |
+--------------+------------------------+
| user         | host.domain.com        |
| root         | 127.0.0.1              |
| root         | ::1                    |
+--------------+------------------------+
3 rows in set (0.00 sec)

Have you unblocked the firewall?

Yes, as we get Access Denied error. So we are getting into the database.

Did you check the my.cnf file for correct settings?

Incorrect settings in my.cnf (/etc/my.cnf) can cause it to refuse connections. These are skip-networking and bind-address. My file looks like this:

#
# This group is read by the client library
# Use it for option that affect all clients, but not the server
#
[client]

#
# 
#
[client-mariadb]

The server file contains the bind-address directive to allow remote connections

bind-address = 0.0.0.0

Did you check the other config files?

Yes.

Does telnet work?

Yes.

Did you remember to restart?

Yes. I restarted using this between all attempts:

service mariadb restart

We cannot find what is wrong with this server.