Try deleting conversation history on both phones and restarting your phone or if you have an iPhone, do Settings>General>Reset>Reset Network Settings. It won't delete anything except your wifi passwords. If that doesn't solve it, reach your carrier for further troubleshooting.
