I too switched to Android after Apple released iOS7 and have been having similar issues. The only solution I've found so far that still doesn't fix 100% of the problems is by asking friends and relatives to log out of iMessage, restart their phone then log back in.