Start Menu Folder Redirection

We have a group policy applied for our users that, in XP, redirects their
Start Menu to a read-only network location so that when they log on they are
given several sets of shortcuts to commonly-used, network-based facilities
and applications (this is in addition to whatever is in the local All Users
Start Menu).

In Vista the exact same policy, rather than copying the shortcuts from the
network to the local machine, seems to want to do the opposite. The Start
Menu items do not appear and the following error message is given in the
event log:

Failed to apply policy and redirect folder "Startup" to "\\Network Location
etc\Start Menu\Programs\Startup".
Redirection options=9028.
The following error occurred: "Can not create folder "\\Network Location
etc\Start Menu\Programs\Startup"".
Error details: "Access is denied.

We now have two problems. Firstly, that we need to be able to do the same
thing in Vista that we could in XP and we can't see how. Secondly, even if we
do find a fix how are we supposed to apply something that works across both
platforms when it is a user rather than a machine policy? We have roughly
1000 PCs including a large number of mobile devices which makes it impossible
to upgrade all our PCs to Vista at once and means that there will be a given
period where the two platforms will have to co-exist.

Any suggestions welcome..

Ben