Is it trying to save to Internal Storage or an SD card? If the latter, see if it still happens on Internal Storage, or with a different card.
Are these long or short videos? If they're pretty long, are you sure you have enough free space on your Internal Storage?
I've had thus happen. I had to clear the cache and then restart the phone. After that it started back working.