It's a little strange that *.mdb files, which should be associated with MS Access are being blocked as you say.
And as for Software Restriction Policies requiring multiple reboots, I've found this too. Not quite sure why, but at least it works (which is the most important thing).
I think the problem 'might' be to do with designated file types. On the server, chances are you may have Word and Excel Viewer installed, but as far as I am aware, there's no such thing as Access Viewer.
Try administering your SRPs from a workstation (using MMC) which does have MS Office installed (so the *.mdb association is created). You may want to install the
Server 2003 SP2 Admin Tools and
GPMC on your admin workstation.