We had 2 BES with ~1000 users, and built 2 new 5.0 BES (same BES Domain). RIM gave us 2 temp SRPs for the 2 new BES, which allowed us to move all of our users into the 5.0 environment without issue. Since it was the same domain (not a new BES domain), CALs weren't an issue. Once we got done with the migration, we called T-Support and had them switch the 'temp' SRPs to be our permanent SRPs, so there was no swapping that had to be done on the new BES. I then simply removed the 4.x BES and that was it!
I'm not positive but I imagine T-support would probably be required for this (we have it), but it was a HUGE time and hassle-saver.
Good Luck!