Update: I tried changing the nickname on my phone, that didn't work after a couple hours. Now, I'm resetting the whole device.
*** UPDATE ***
Well, a complete de-register and re-register did the trick.. not sure why that was required but at least a user serviceable fix.. all phones are now connected again - well, it was only the new phone that was having the issue.