After weeks of umming and ahing and a couple of guys at work switching to SPDs, I got myself some Shimano pedals (off road type jobbies) and Bontrager shoes from my LBS yesterday and I'm pretty impressed so far. I have only done about 20 miles so far but I don't have any aches or pains and (touch wood) haven't forgot to unclip my left foot at junctions yet. I'm unclipping nice and early at the moment.
84 quid all in they cost me which I thought was a decent price, and the guy at the LBS set them up for me and came outside and gave me some instruction in the pouring rain as I rode up and down the wee cul-de-sac next to the shop getting familiar with them.