Be mindful that despite their branding, these hubs are not meant for heavy loads; rather, it is their intention that, when stopped, the rider shifts to a low enough gear that they are spinning the bike up to speed, rather than mashing up to speed in a high gear (which is how the majority of novice cyclists destroy their knees and ruin their commutes).
Here's what I think happened: you got your new bike, but the work of bedding in the cables wasn't done to completion. As a result, during your rides, your cable was "stretching" into the inside of the housing, leading to a misalignment of the gear cable. When your LBS replaced the wheel, they had to reset the cassette joint and cable, which would have improved the performance, however, if you still had break-in left on that cable, shifting problems would have returned.
At any rate, there are really only three likely possibilities:
1) The cable is not aligned properly.
2) The hub internals are damaged.
3) You are using it incorrectly.
The first possibility is easy to rule out. Familiarize yourself with the indicator markings on the hub cassette joint - the part of the hub that swivels around to change gears. There are two yellow marks on the underside of the hub that must align perfectly in 4th gear (for 7 and 8 speed Shimano IGHs). The markings on the bottom are easier to see than the window at the top, but require a work stand or flipping the bike upside down. If, after every episode of skipping, you check the cable and the indicator markings are lining up perfectly, then you have successfully ruled out the cable as being misaligned, which is the most common problem with these hubs.
The second possibility requires no explanation. There is practically no way to positively determine that a hub is defective: you merely have to rule out the other possibilities.
The third possibility is exceedingly common. Perhaps your bike shop didn't prime you for what the hub is actually capable of. Perhaps you're shifting under load (do you stop pedaling immediately before shifting, then resume your cadence only after you've shifted and confirmed the shift by feel?) Perhaps you're simply trying to put too much torque into the hub. Are you a heavy rider who likes to stay in a high gear? If so, you can expect the worst performance from your parts: learn to love low gears and learn when to coddle your parts and when it's ok to put down the watts.
A few other notes:
The tension of your belt is almost certainly irrelevant. However, a loose belt may correlate to skipping/grinding issues because if your wheel has slipped forward in the dropouts (or, as the case may be, your dropouts have shifted forward in the frame), that could affect the tension on the cable (it depends on how the housing is routed; if the housing stops at the cassette joint like it should, it won't have any affect; if, on the other hand, the housing stops at a frame braze-on then your wheel must be exactly in the position that lines up the indicator markings in the appropriate gear. I can clarify this if you think it may be the problem).
Frames, especially steel frames, can have considerable flex in them. You can sometimes see the bike flexing down at the bottom bracket when mashing up a hill, especially on older bikes with thin tubing like Reynolds 531. We see a lot of "ghost shifting" on vintage bikes with friction shifters because the flex of the frame under heavy load physically yanks the cable. You could be simply mashing too hard and pulling the cable - even a millimeter would throw the planetary gears out of alignment and cause problems. The solution to this is to alter your riding style: shift yourself into a nice low gear when at a stop light or beginning an ascent. Gradually increase your gearing until you hit your desired speed.
