Have you tried plugging a computer into the ethernet port of the newer Airport and run the Airport utility to make sure it's still configured properly?
If you have or if it is, I"d next check and encryption you have enabled such as WPA2 to make sure that the key hasn't become corrupt. In other words reenter the key/pass-phrase on the airport and on the computers. If you are using encryption, try temporarily removing it and see if the computers can connect.