That's an interesting issue. Sounds like the new brake switch is bad.
There's two sets of contacts. One for the lights, and one for the shift interlock and sends a signal to the LCM.
This signal is used as a redundant cruise control deactivation (in addition to the dedicated cruise deactivation switch at the top of the brake pedal), and for various programming procedures that require a brake pedal test.
Sounds like this second contact isn't working.
Member of Northwest Panthers Car Club
2008 P71, Norsea Blue SAP
-Message Center cluster retrofit
-Towncar Signature L heated power seats
-Long overhead console
-Compustar remote start/security