Win 2K Pro Display Schemes

Our 6000 users have recently needed to change the default desktop resolution from 800 X 600 to 1024 X 768 to accomodate a new application. This makes everything on the screen much smaller and they don’t like it. I have tried to change the display properties, appearance, scheme to a different, larger scheme but the systems all freeze. Users with Admin rights can change it with no problem but just “normal” users can’t. How can we allow this without giving everyone admin rights?