It seems most of the payment gateways around at the moment are poor at best. I understand that building a new payment gateway from scratch would be a huge job with an even larger budget, thankfully something that isn't too much of an issue If anyone has any information on laws that would need to be followed, licences that are required etc, it would all be greatly appreciated
You would need to be PA-DSS compliant, (https://www.pcisecuritystandards.org/security_standards/pa_dss.shtml) and you would need to contact processing platforms to get licenses to integrate with their systems. Here's a really basic chart on the platforms in the US - http://www.merchantaccountblog.com/141/processing-platforms. The largest are FDR Nashville, and Omaha, Nova, Vital, Paymentech, and Global. There are also a number of international platforms, Pago, Moneris are the big ones off the top of my head. The most difficult part would probably be obtaining the licenses and integrations with the platforms, and full-redundancy. Authnet just had a major mess-up last month, and something like it would probably kill a startup. Since you will be storing and transmitting card data, security will be obviously be another a huge issue.
Yea after a bit more reading it's looking like a good years work before things would be up and running, and that's with a full team. Hopefully one day, but not in the near future