It's a 7805.
ICs frequently come in different packages. The 7805 is one of those that has been around long enough and is so popular that it comes in several varieties. Between 30 seconds with google and the parts I've seen in person, there are at least:
D-PAK package - the packge on the Arduino NG
TO-220 - the large package you're probably used to seeing
TO-92 - typical package for discrete transistors, also used by the 78L05 and the DS1820 1-wire temp sensor
SOIC-8 - surface mount package
... and National has a tiny thing they call a bump SMD or something like that.
I want to say I've seen it in SOT-23, but I could have dreamed that one up.
Vendor part numbers vary a bit, too. I think a likely designation for the Arduino NG's regulator is 78M05. Letters after the number are sometimes vendor specific, and tell you things like tolerances, temperature ranges, or what sort of packaging they're shipped in.