There's lots of kinds of distortion and I think there might be some talking at cross purposes here.
The one that usually claims general use of the term is geometric distortion, which is where straight lines towards the edges of the picture appear curved. It's a lens defect and can be barrel or pin-cushion shaped, and either a smooth curve or a wiggly curve (moustache distortion). Easily corrected in post processing, though moustache is more tricky. (Canon has custom corrections for this that can be automatically applied in their [free] Raw processor DPP. Don't Nikon have this too?
)
Perspective distortion, where objects closer to the camera appear relatively larger, is purely a function of shooting distance, as described above. A tilt/shift lens won't help with this in the situation described. I prefer to call this exagerated perspective, if only for differentiation. With the more distant shooting position using longer lenses, the opposite applies and perspective is flattened/reduced/compressed.
Then there is the stretching distortion you get at the edges and corners of images shot with a wide-angle lens, where things get pulled out of shape - badly out of shape with super-wides. Don't use one for group photos, or at least keep important areas of the subject away from the edges. I've got a feeling this might be Gary's problem? It's an unfortunate side-effect of rectilinear correction - basically if the lens is properly corrected for geometric distortion, things get stretched. So again, not really a lens defect and all wide-angles do it the same at similar focal lengths
The other thing to mention in the context of perspective distortion is that when you move close with a wide-angle, the field of view gets much bigger. Even though the main subject might be normal size in the frame, there will be a lot more background visible behind than if you'd stood back with a longer lens. This is the main reason why longer lenses tend to give better subject isolation and subjects stand out better from the background - better bokeh. Most people think it's a depth of field effect but since DoF remains the same if the subject framing remains constant, that's not it. It's a bit of an optical illusion maybe but, depending on how much detail there is in the background, it looks real enough.
Edit: Just a note: the 'natural' imaging state of a lens is generally spherical and a lot of these issues are to do with the way this is corrected in lens design. Basically an uncorrected lens will produce a fish-eye type image, with strong barrel distortion. The subject field of sharpest focus will also be curved, and so will the image projected on the sensor. Rectilinear design corrects geometric distortion by pulling out the corners of the image to make them straight. The same thing has to happen on the imaging side because the sensor (film) is flat.
A lot of lens design effort goes in to sorting out these things and it is an interesting prospect to consider what might be possible if we had a curved sensor (basically saucer shaped) and geometric distortion was corrected in software. Actually, the latter is already happening in some compacts without our knowing as the only image we see is the processed JPEG shown on the LCD - we never see the actual optical image projected by the lens. I think we are going to see more of this with ILC cameras (interchangeable lens compacts like the Panasonic GF1 and Olympus E-P1) which could result in sharper, simpler, cheaper, smaller, lighter lenses with greater zoom range and lower f/numbers - or at least some of those things.
Feel free 
