I found the answer to this issue. An administrative profile we have been applying to include our wireless network settings was changed somewhere along the way. The new profile disabled and was hiding the Wi-fi Protected Setup option 'Enable registering other devices'. Enabling the option causes Wi-Fi protected setup to work the way the laptop users were used to.
Editing that Administrative profile and applying it to the new laptops solves the problem.