I'll assume from your post you are in the UK.
Are you using the Barclays gateway (ePDQ) or another gateway such as Datacash, Secpay, Protx etc?
If you're not using the Barclays gateway, it's worth speaking to your gateway as they may be able to offer advice and recommendations - many have negotiated good rates for their clients in return for recommending one of the banks.
The main Merchant Account Providers in the UK are:
Bank of Scotland
Euroconex may be worth a try, though I have no experience of them.
I have no experience of using an overseas merchant account (e.g. a USA one) but I personally would avoid this route.
Of course, before you jump ship, make sure you speak to Barclays and get a rate review if not already done! Most banks will do one every 6-12 months, and provided you have a good track record and low chargebacks then they will usually review rates favourably.
Getting competetive quotes from other banks to wave at Barclays would probably help too!