How are you doing your moves - have you tried using the built-in MOSS
structure editing tool?

To this point, the user  has been trying to utilized copy/paste with explorer
view. What structure editing tool are you referrring to?

From the MOSS "Site Actions" menu (you'll need to be a site  and/or site
collection admin depending on exactly what you plan to do) choose
"Manage Content and Structure". This will show you a UI that will allow
you to copy/move items, lists, and sites around in the site collection
structure.

I have a feeling that that option isn't available with the standard team site
option. I see it in collaboration and publishing templates but not using the
team site  template.

Yes, that is correct - it's a MOSS feature so it's not available in site
templates (like Team Site) that only include WSS features. Activating
the SharePoint Server Publishing Infrastructure feature in the site
collection should make this menu item appear - you can always have them
disable the feature afterwards if needed.

You can try a couple of things. To get to the site  manager you can
try using the url:

http://servername/_layouts/sitemanager.aspx

another option you may have might be to open the site as a network
place. Add a new network place, when it asks for an internet address,
give it the address to the site where your doc library is located
(eg. http://servername/site ). This should open a folder  letting you
see all of the document libraries and lists inside your site. Just
find the folder with the name of the document library you want and
move it where you need to. You may have to create a network place for
the site you plan to move it to as well.