Open regedit while logged onto an account with admin priveledges. In regedit, open HKEY_LOCAL_MACHINE. Click on File (at the top) and select Load Hive. Navigate to c:\documents and settings\default user. The file you want to open is NTUSER.DAT. It will ask you to name it- call it Default User. Now it will show up as "Default User" under your HKEY_LOCAL_MACHINE. Go into Default User->Control Panel->Desktop and find the Wallpaper key. Just put in the path\filename in place of what's already there. That will change the wallpaper for all new users logging into the system. Now, assuming you still have regedit open, go back up until you're resting at Default User, now click on File->Unload Hive. Now create a new user and login and see if the wallpaper is changed. Be aware that the wallpaper you put in must be located in an area where everyone has at least read access permissions.
Yes thanx Wrathchild. I had the same issue and this worked perfect for me. However I would also like to create a batch file that will do this as well as drop the wallpaper image file into the Window\web\wallpaper folder. I have several thousand machines this has to be done on and I would like to make a package for this using Altiris to push out. If not i guess I could just make a RIP.