If the windows are new, are you sure the problem is the windows? If they're double panes and new(ish), it may well be worth checking on what kind of insulation is in the walls. If the answer is "not much," I can't speak highly enough of spray foam insulation. It would be a major PITA while it was going on, but then you'd have serious soundproofing and insulation in one.
I'm sitting in a room with five windows and a sliding-glass door and I can't hear the birds singing outside or the nearest neighbor's dogs (said neighbor is about a quarter mile away, but he has a full pack of hunting hounds, so there's some considerable noise). The windows are new double panes, but they're the cheap ones, not even double hung. The walls, though, are full of spray foam, as is the roof deck. This place is so quiet I jump when the water heater kicks on (it's new, too, and not at all loud).
Spray foam has the side benefit of being kick-ass insulation, too.