Well, please let me know which ones you mean, because all of the following have serious barrel distortion issues at 18mm:

18-55mm, 18-55mm VR, 18-70mm, 18-105mm VR, 18-135mm, 16-85mm VR (the best of a sorry bunch at 18mm), and 18-200mm VR (more expensive, but still has the aforementioned problem in abundance).
I can't seem to find any other Nikon AF-S zooms besides these that can be bought for under about $800, and none of those above pass muster for delivering straight, undistorted lines at 18mm.

The only Nikkors that do are the 12-24, the 18-35 non-AF-s, the 17-35mm f2.8, and the 17-55mm f2.8, and only the non-AF-s 18-35mm is within the budgets of many D40/D60 owners - but, again, with no autofocus on those cameras.

If, on the other hand, you feel that any or all of the lenses I listed in the first group above are perfectly good at 18mm, then we'll simply need to agree that you're a lot less critical about your wide angles than I am. Because they all suffer badly from linear distortion at 18mm. I need a wide angle that renders straight lines as straight, not as arcs.

Neither the 12-24 nor the 18-35 render "straight lines" at 18mm. They both have visible distortion.

Barrel distortion is an as-of-yet unavoidable problem with extreme wide-angle lenses, particularly wide-angle zooms.

Even my $1700 14-24 f/2.8 [which is currently the best lens of it’s kind regardless of brand] has some distortion at 14-16mm.

The Nikkor 12-24 at 12mm has mustache or complex distortion which is very difficult to correct. From about 15-18 it has simple barrel distortion which is easy to correct but there none-the-less. The truth is that in absolute terms that lens really doesn't shine until about 20-24 and, IMHO is significantly over-priced for a lens with consumer-grade build and an f/4 maximum aperture.

The 18-35 is another mediocre lens that also has visable barrel distortion in the 18-22mm range and it is woefully soft in the corners until f/8, it also flares like a SOB and has problems with chromatic aberations [color fringing] to boot.

I'll take your word for that, since I don't use the Nikkor 12-24 lens (I have heard that both Tokinas are better). That's why I prefer primes at the wide end. I am pretty darn pleased with my 14mm f2.8 Sigma lens (at least on a DX camera and a 1.3x crop camera (Kodak DCS-760). Although I've heard that this lens is soft in the corners of a full 35mm frame, I've only tested it on DX and 1.3x crop) My "tests" of this lens in full frame have been severely limited to looking through the viewfinder of my Nikon F2. I have yet to run a roll of film through with it.

I agree that it flares, and that it's soft in the corners wide open. As for barrel distortion, it's much milder than the wider range kit zooms. All very wide lenses flare. Anyways, I am new to the world of distorting wide zooms. Coming over from the Olympus system, where they make two SUPERB wide zooms (the one I used was a fabulous 11-22 f2.8~3.5 with negligible distortion, that also cost me under $600), it's been frustrating to find any wides in the Nikon system that compare, other than Primes or very expensive FX zoom lenses that are overkill for DX bodies.

To your surprise, most of these came $100-$500. I lucked out on a used 17-55mm and the 12-24mm cost a tad over $400 used. The 18-200mm came on the D200 as a kit and it must cost close to $700 standalone. We needed the 105mm Micro for work and it cost around $800 new.

So I don't know why you keep on saying they cost over $1000. You might have done a good job looking for primes. Other people have done good jobs looking for AF-S'. I am in Tokyo this week. I will browse camera shops when I have time.

Yodabashi Camera: Heaven on earth!
http://www.photoness.de/yodo_analog/

Yes, also BIC Camera in Yurakucho. I will be near the Yodobashi store on Saturday.

The Softmap stores at Akihabara has a used equipment department that has good deals sometimes. For instance, I got our D40x body cheap when the D60 came out. Used equipment are warranted for 30 days and any missing items are noted on the tag.

I got a Canon 35-105mm FD one ring for $10 in Nipponbashi in Osaka last trip. Yen at Y89/US$ hurt to some extend.