Thanks for all the replies. The bike is new so it could have only been over tightened by Evans on its 4 week bed in service. As I said the right one came off no problem.
I didn't mind about trashing the pedals as I was replacing the factory pedals with SPD's.
In the end I drilled through the pedal arm, then used a strong peice of steel through this to turn it off. It came off fairly easily.
I had to get a titanium bit (£5 for the one), and it took around 3 or 4 minutes to drill, and after that the bit was shafted.