I know its a pain, but backup/restore can only work between the same version because there is no "upgrade logic" built into it - its a simple dump/reload tool.
The only route I can think of is to take a backup of your 3.1 server and restore onto a 3.1 on another intermediate machine. Upgrade that to 3.3 then 4.0 and make another backup. You can then restore this onto 4.0 on your final target 2003 server. Ick (sorry)
I messed around with CSUTIL and was able to dump and import users and groups, but not the NAS devices. In the end I decided I'd waste more time trying to export/import the NAS devices than it would take to manually re-enter them.
Thankfully, whoever set this up originally used wildcards for the entries for all our branches (~700) and configured the branch routers with the same key. Not necessarily the most secure config but much easier to manage. So, there is only maybe 10 entries for all our stores based on a class B address with a wildcard (eg. 10.1.*), then all the entries for switches/firewalls etc at the head offices.
Maybe this info will help someone else doing the same/similar upgrade in future....