Bullsheet.
I've built a UNIX server, run MySQL on it and use Access clients against that MySQL server.
(they may thinking of different protocols but ODBC is fundamentally client-side; as long you have MySQL ODBC driver installed on your users computer, that's all they need)
PS: On second thought, if they meant to say they don't allow remote connections to their MySQL server, that may be why they said that. Not all hosting plans allow you to have remote connection to the resources other than the web. You may need to upgrade your plan or get other hosting provider that allows non-web-connection or maybe just provide a mean of logging in the server using SSH.