Lock nuts on new hubs seem strangely tight, but can't seem to loosen them. Any advice?
Those counterlocked axle nuts are binding together more tightly than the threads are on each individual nut, and thus staying counterlocked against one another. Usually this isn't the case and when you put a wrench on the outside nut on either side of the hub, one of the outer nuts will break free. As you're seeing now, not always the case.

You need a box wrench and a cone wrench (or two cone wrenches) to break the inside and outside axle nuts on one side free from each other. Then get the bearings properly preloaded and counterlock them again. This process can be tricky as the preload on the bearings will change as you counterlock the two nuts back together. It usually takes a few tries to get the preload set right and the nuts counterlocked firmly. Too tight? back them both off 1/8 to 1/4 of a turn and try again. Too loose? Do just the opposite.