I am using 1st Contact to set up a Barclay's International account. Yes it costs $50 AUS for them to set up the account for you, but their customer service is outstanding and they have a whole range of services that go beyond banking. It is worth a small fee to have a fully functional bank account when I land in England without having to wait for a permanent address.
