Хочу поділитись, як вдалось вирішити проблему. Як виявилось, це Андроїду не подобались налаштування хот-споту, тому він не міг підключитись. Оскільки на телефонах, які не хотіли підключатись, не було можливості примусово заставити їх підключитись (не допомагало навіть ручне налаштування підключення), потрібно було змінити налаштування хот-споту комп’ютера. Всі дії зі стандартною програмою налаштувань до бажаного результату не привели, тому вирішив пошукати щось для Лінукса, що дозволило б більш розширено налаштувати хот-спот. І на диво швидко така тулза знайшлась (не вважайте за рекламу - сам тільки про неї дізнався). Називається вона linux-wifi-hotspot, взяти можна з Гітхаба. Додатковим плюсом цієї дійсно хорошої утиліти є те, що вона дозволяє одночасно використовувати один Wi-fi адаптер і для прийому, і для роздачі (на кшталт Windows), а також дозволяє відкрити на екрані комп’ютера QR-код, який можна просканувати телефоном для швидкого підключення.
Сподіваюсь, ця інформація комусь також допоможе.