heh ... conveniently 3.6 doesn't use the database all that heavily. In fact when you upgrade from 3.6 to 4.x you can all out trash the database if you don't need to worry about any IT Policy info and you have your licenses backed up.
I'd recommend giving TSupport a call, just so you get a complete solution and have someone hand-holding.
But if you wanted to fiddle around, you could use the createdb command to create a shell database and point the BES to that database. Personally ... I'd plan an upgrade to 4.1 SP4 and have it create a new database. Once you get to 4.x though ... please make sure you do some backups