We have recently done a similar migration, we went from Domino 7.0.2 to 8.5.1 and BES 4.1.6 to 5.0.1 MR2. I would upgrade your Domino servers first and then the BES server. We also went with the migration process and found that it worked very well. We migrated about 350 users, and our sucess rate was good. If you have questions you can contact me.