While AI technologies and tools offer various potential benefits to their users, it is not clear whether opportunities to access these benefits are equally accessible to all. We examine this gap between availability and accessibility as it relates to the adoption of AI-Mediated Communication (AI-MC) tools, which enable interpersonal communication where an intelligent agent operates on behalf of a communicator. Upon defining six functional AI-MC types (voice-assisted communication, language correction, predictive text suggestion, transcription, translation, personalized language learning) we conducted an online survey of 519 U.S. participants that combined closed- and open-ended measures. Our quantitative results revealed how AI-MC adoption is related to software, device, and internet access for tools such as voice-assisted communication; demographic factors such as age, education and income in the case of translation and transcription tools; and some components of AI-MC literacy for specific functional tools. Our qualitative analyses provide additional nuance for these findings, and we articulate a number of barriers to access, understanding, and usage of AI-MC tools, which we suggest hinder AI-MC accessibility for user groups traditionally disadvantaged by one-size-fits-all technological tools. We end with a call for broadly addressing accessibility concerns within the digital technology industry.