Windows

That's a hard thing to do in a week day. It should be done in a long weekend, preferebly.
First thing to do reduce the renew time to 1 day in DHCP (last day of the week Friday, so by the time you start, all the IP leases will have expired). then, create the new scope in DHCP, then assign the servers with the new IP, then delete the DB in WINS, finally, update your DNS and remove all, but the PDC from Server Manager.
First, Reboot the PDC, then the BDCs, then all the important services servers(WINS, DHCP, RAS, etc...). As you boot each server, add it back to Server manager, one-by-one as you reboot it. Allow for WINS to rebuild the DB. Finally, update any static routes on the router and reset your router.
It should go pretty smooth then.

Good luck!

You don't mention the exact configuration of your network, however you do not need to remove anything from server manager. The wins database will update itself as the computers register. It sounds like you have everything correct but you do not mention if you set the routers to forward the dhcp packets. Your routers need to have bootp forwarding or a dhcp helper address. If routers are not between the clients and the DHCP server then I would try to sniff a client and see what is happening.

calves mentions reducing the DHCP lease to 1 day - this may work, but depending upon timing you may need to do an ipconfig /release on your workstations and then reboot in order for them to obtain a new address from the new DHCP scope. It sounds like this was where your problem lay the first time - the workstations were holding on to their old IP addresses because their lease time had not expired. Hope this helps!

Just add a DHCP Relay Agent on each subnet that does not have a DHCP server or allow your router to pass BootP broadcast.

Your routers are already configured in Class C subnets as noted in your above statement, so I would do the following:
1) Change lease time to 1 day on DHCP scope for each subnet.
2) Change the scope of each subnet (not create new) to fit within the class C sunbet of the router, while leaving the subnet mask at 255.255.0.0.
3) allow the change to propigate(this will depend on your current DHCP Renew time settings.)

Once all the clients are within the class C scope of the router, you should be perfectly safe to to change the scope again, this time changing the subnet mask to 255.255.255.0
once this change has propigated, change the servers subnet mask to 255.255.255.0

most of all, make sure the router is within your class C scope,or they will only talk localy.

Good Luck