I learned this today because I followed some links off an article about George Carlin that were poorly coded. Those links took me to Salon's 404 page, which uses Salon's standard layout, _complete with ads. _That is a major faux-pax; when the user is lost, the last thing he or she wants is to be sold to. I understand that Salon needs to make money and ad impressions are its chief vehicle for doing so, but the add blare was such a major turn-off I almost gave up struggling to find what I wanted.
The 404 is incredibly unhelpful. So are most in the galleries you might find on the Internet. A 404 ought to make a positively heroic effort to decode what you were trying to do and help you find it. If you recently re-arranged your website, hopefully the arrangement has some sort of algorithmic relationship: "pages named x-y-z.html can now be found in y/z/x.html," for example. Helping people find that relationship for themselves and understand your new layout is far better than just saying "Er, you screwed up."
PS, It's "We screwed up." Never blame the user.