I got a set of budget 27's with Quando hubs. They haven't done a million miles but they've never been a problem. As Joe says though, it's cheaper to buy a whole wheelset than it is to pay to have your existing ones re-laced. Unless you have rims or hubs that are specifically worth keeping, it's not work it. That said, a set of spokes and a spoke key is even less and there's a guide how to lace wheels on Sheldon Brown if you want to have a go. I've built a few sets using that guide http://sheldonbrown.com/wheelbuild.html
A set of eBay straight stainless spokes is about £12-16. I think double-butted ones from Cycle Basket (by far the cheapest - and nice spokes) work out about £25 with the postage. It's a couple of hours work even for an experienced bike shop, so that's where the cost is.
On the sizing of hub axles - there are a few sizes around. Some of my older nutted front wheels have had a nut slightly bigger than a 13mm but too small for a 14mm spanner. It was a Whitworth size (3/8" Whitworth maybe?). Also, the axle on my metric size track hubs (15mm nuts) is too big for two sets of my forks (70's bikes) and I had to file slight flats on either sides of the threads to get them to fit. I've found bearing locking nuts have been all sorts of sizes, so I just made sure my bearing adjustment spanners are double-ended and cover a range of sizes.