Thanks for your advice! I used an AVRISP mkII to program the board. (Or, at least, I think I did; the programmer has "AVRATAVRISPMKII" written on the back and looks like this: http://www.atmel.com/Images/AVRISPmkII.jpg
). When I plug the Arduino in now, it starts up much, much faster; almost instantaneously rather than the 8-10 second wait that I saw before. Unfortunately I get the same messages on Windows machines about installing Arduino drivers.
Maybe what I did is not exactly what you recommended. To program the Arduino with the AVRISP, I used the 1.0.1 IDE, selected AVRISP from the menus, and held shift down when clicking the upload button so that it says "Upload with programmer" or something like that.
Does that sound about right? Do you have any other ideas about what this might be?