It may be important here to distinguish between the Android operating system and the Google Play Store. Your app should continue to work fine on Android--this is just a policy "feature" of the Play Store that Google will not publish apps that use the SEND_SMS permission unless they are intended to be the default SMS app for the phone (which your app is not). There are some exception and you must fill out a form to be considered. We tried to do this for the MIT AI2 Companion app and were rejected. You may have better luck than we did.