Personally, if they've given you a quote like that, told you replacing the tyre is optional, and it'll still get regular punctures, I'd be looking for a new bike shop before I looked for a new bike.
The vast majority of punctures are caused by tyres that are either worn or not fit for purpose, and replacing the tyre with something suitable solves them (and you can get puncture resistant tyres in all shapes and sizes). Also, I'd question replacing the rear wheel because the brakes are rubbing. The brakes could be set up badly, or the wheel could need truing. It's possible you might need a new wheel, but not very likely. I don't know any bike shops in London, but I'd be very suspicious that they either don't know what they're doing, or they saw someone inexperienced come in the door, and their eyes lit up.
However, if you want to buy a new bike rather than solving the problems with your current one, there are probably a couple of sensible options. One, as has been said, is a tourer. Another is a kind of road-ish hybrid, but with a slightly tougher frame than a road bike, and the capacity to take wider tyres for comfort on the towpath. Or you could look at a cyclocross bike (like the Boardman CX that has already been recommended). They're capable off-road and quite quick on-road.
Probably the biggest decision you need to make is whether you want dropped or flat bars. There are pros and cons to both for commuting, so knowing which you want, and also knowing whether you want a more or less upright position, will help to point you towards the right style of bike.
