The correct procedure is the one you followed. Create a backup, install OMV, run omv-regen, and rebuild from the backup. If you have omv-kernel installed, it will ask you to reboot mid-process and run omv-regen again to finish.
I have no idea what the problem could be in your case. Please tell me the output of dpkg -l | grep openme and I'll try to recreate it this weekend.
Are there any special conditions in your hardware or software system?
Did you check the omv-regen log for errors?