I was having the same problem and I just fixed it by clearing all my old messages out of my deleted folder! Guess the phone had no room to record anything else? Idk... But it worked hope this helps! Worked!! Thank you!
