A couple things to check.
Is the user logged in when you run the script? If not it can't run the script as the current user plus there will be no HKCU hive to even import the settings into.
Are you using regedit to import the key? If so, does the user have rights to use regedit?

Yes, I am logged in as myself through RDP to my test XP machine. I am a local administrator of the box. WHen i run the REG ADD command locally from the box it makes the changes i want. But when i deploy from DS i get nothing.

It may not be working due to using RDP.  What happens if you are logged on locally to the physical console of the machine?  Or if that isn't possible, can you connect using MSTSC.EXE /CONSOLE /v:computername  (or if you're on SP3 or are using Remote Desktop Client  6.0, use /ADMIN instead of /CONSOLE).  You can verify you're in the console session on the Users tab of Task Manager.  The Console session with have a Session ID of 0 (errr, I guess on XP there isn't a Users tab, so in Task Manager's Processes tab, click View --> Select Columns... and check "Session ID").

I don't think logging in through RDP is going to be the same as being in front of the computer logged into it. If possible you should try that.

I tried the same thing and for some reason I couldn't it to work in DS.  My work around was to use NS and run it as logged on user.  May not be a solution for you, but it did work for me.

I am stretching here but is it possible you need to call the path to regedit or reg add?

Can we see your whole command line?

Did you try cmd.exe /s start reg.exe

or

cmd.exe /c reg.exe

Sometimes that seems to work for me..... give it a shot. You could also try running a vbscript

Dim oShell
Set oShell = CreateObject("WScript.shell")     <-- object you will need to use unless you go the wmi route.

One other option, and it is not that great, is to have your script drop an entry in the ActiveSetup settings in the registry.  The next time the user logs on, the user-specific additions will be added to their profile.  You know when you upgrade Office or IE or something and the next time you login you get a small gray box "Setting up personalized settings for..." in the upper-left corner?  That's ActiveSetup in action.  There's an excellent write-up by another of the Trusted Advisors (EdT) here:
http://www.etlengineering.com/installer/activesetup.txt  and some more from WikiDesktop:
http://wikidesktop.org/index.php?title=Active_Setup

Just an idea for you..

'Set registry key
'vbscript

Dim oShell
Set oShell = CreateObject("Wscript.shell")
oShell.RegWrite "HKLM\Software\Microsoft\Windows\CurrentVersion\Runonce\command","reg.exe import \\altiris\express\regfiles\zack.reg","REG_SZ" 

Use run once, change command to whatever you want, force user logoff. Next time they login it should run.