Yes, being a small ISP, A&A are quite expensive if you're a 'heavy' user - they can't afford to subsidise the heavier users like the huge ISPs are able to, but if you're stuck with a line no-one else is willing to get fixed, they're always an option given their guarantee to get it fixed or your money back. You don't necessarily have to stay with them outside of the minimum term, just perhaps keep a closer eye on your usage while you are.
I don't suppose you still have the router running to check line stats? They could be useful for determining where the problem lies. I just wouldn't take customer support's word as final when it comes to technical issues - my experience with BT's call centres is pretty terrible though their UK staff are generally good. It's just a shame it's more of an effort to get to speak with them.