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)