You're right...gotta have MySQL to use YaBB SE. I transferred my old YaBB 1 Gold over to my new host and then converted successfully from there. I suggest you keep your old host until you have converted your board and everything is fine on your new host. Just in case.
I'm gonna check out
http://www.cyberwings.com as my new host. I hear their support is great.
http://www.smartrat.com is my current host and they have changed their "unlimited bandwidth" to 20 Gigs a month so I gotta move. I was also looking at
http://www.siteturn.com as another possibility.