User settings are stored on both the BB and the BES database as part of the wireless back.
Seeing as the users are no longer on the old BES and you cleared the BB info from the mailbox, they won't get it back
The only way you could have saved the info would be to back up each device and restore the content database.
As of they have to set everything again and get any ringtones they may have lost.
The wireless backup of the BB's do not backup any data as well, only user settings.
Data is kept in Exchange but EA only syncs the last 5 days worth or 200 messages, whatever comes first.
Maybe this will teach the users to perform a backu here and there