I am having some issues with my Magento site. I have 2 backend guys on it and they cant get to the bottom of it.

It started off with this error this morning 

> Error: SQLSTATE[HY000]: General error: 2006 MySQL server has gone away

When a customer has enters their delivery/payment details and clicks complete the order it  hangs for 1-2 minutes and then returns the above error.

We figured out that if a customer pays with paypal it goes through perfectly. Also with some credit card transactions, we noticed that some go through but we still get the above error.

We have increased
`max_allowed_packet` and `query_cache_size`

Any help would be greatly appreciated asIi am not a techie and my techies can't figure it out

Magento 1.9, Onestepcheckout

(`max_allowed_packet` is not the issue here)