Re:
Any decent LBS should be able to build up a set of wheels. I used to use Carrick Cycles in Ayr when I was a laddie - in fact I still have a set of 217CD they built up on to XT hubs for me around 15 years ago, and they are still going strong!
Price wise, if you are getting the shop to supply new spokes, nipples, tape, etc then you are probably looking at around the £30 mark in parts, and maybe £15/£20 in labour (depending on their rates) per wheel.
You might be able to get it slightly cheaper by providing your own parts, but for the sake of £5/10, support the LBS and get them to do it! Plus, if there is only one false economy applies in bikes - its cheap wheels!!
I've heard Doolies in Paisley also have a good name for wheel building, but not sure if that is too far from you.