Today, one of the most senior people at work came to me with their iPhone 3gs which they claimed would reboot approximately 5-10 minutes into a call.

He said that he had tried rebooting the phone, had tried restoring the firmware, and contacted the iStore who said it would have to be sent away to be fixed.
I decided I would have a look first.

Obviously I did what any good techy would do first and googled it.

It appears to be a pretty discussed topic, and appears to be limited to iPhone 3gs on IOS 4 and above. Example discussions can be found:
On the Apple Support Forums
On the Neowin news

This issue has been around since Jun/July 2010, and nobody seems to have a fix laid out in black and white.

The Solution

If you suffer from this try taking the battery out, and putting it back in again.
I did this on my boss’s phone, and it worked! All you have to do is take the screen out. Then unplug the battery cable, number 5/6 (they are clearly labelled). I can’t remember which number it was, do both to be safe.

I followed this guide to take it apart:

But it really is dead easy.
Then put it all back together, and test it. It all worked perfectly for me, although your mileage may vary, and as usual I accept no responsibility for anything