I am having this same issue with a 16gb playbook. It will randomly stop and say device full, when plenty of space is available, and I can start a new recording after it tells me device full. I have had it happen after 2 minutes @ 1080P, 4 minutes @ 1080P, and 24 minutes @ 720P.
When ever I read a thread like this I try to duplicate the problem. So I started recording a video and after about a minute I get the same error. I call tech support and the girl asks me to duplicate it. I try 3 times and no luck. I was able to make 3 videos from 2.30 - 4.0 minutes in length and no error. They gave me a case number that will stay open for 4 days.