GCO is currently free, and if you do adwords advertising the cost can be greatly reduced.
We implemented it a while back, and it instantly become more used than paypal. Personally, i would offer it in addition to paypal. Since most countries aren't supported with GCO, it isn't a subtable replacement for paypal.
Implementing it is a pain, but I think that there are probably more support and ready made scripts, than when I integrated, which was a few weeks after it was released.
Here's the review I wrote a while back.
http://www.merchantaccountblog.com/archives/190