So-I went home and called a different branch. Guess what? No problem.
I would say to push a bit further when they say "declined" or "not possible" oftentimes you are working with a rep who can't be bothered to look into something they are not familiar with. Just sayin'.
This. The knowledge & training of staff from one branch to the next can vary
greatly, just as your mileage can. Keep going up the food chain if you need to.
I think it's pretty funny when people recommend X bank or over Y bank - really they're all about the same.

FWIW, the most recently published FSA data (for the period of January-June 2010) showed that Lloyds had the highest number of customer complaints, followed by Barclays in second place, and then Santander in third. Bearing in mind, these figures may have some relationship to the various banks' market shares - more overall customers could result in a higher number of overall complaints.
Out of those complaints, Lloyds did best at resolving issues within 8 weeks (97% of cases), followed by Barclays (91% of cases), with Santander last (only 46% of cases).
Cooperative is one group that has received higher customer satisfaction ratings.
Another thing to consider, apart from the main commercial high street banks, is going to a building society group (not all offer current accounts though), or a
credit union if one is available in your area for which you are eligible.