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 - 2minutes 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 transationa, we noticed that some go through but we still get the above error.

We have increased
max_allowed_packet, 
query_cache_size, 

Any help would be greatly appreciated as i am not a techie and my techies cant figure it out

Thanks
Fabio

www.Funkychritmasjumpers.com

Magneto 1.9
Onestepcheckout

[max_allowed_packet is not the issue here]