OK. I've found a new host after talking to some people, reading reviews, and talking to the sales people at bluehost.com. The sound quite a bit better than my current host. I'll probably make the move sometime in the next week.
Basically what I'll attempt to do is setup the new host with the new YaBB forum (2.3.1) and migrate the existing forum data over. Once I have that up and running, I'll make the official DNS switch, move the latest forum data from this host over to the new one, and that should result in the least amount of downtown for people. It should go pretty seamlessly, but there is potential for a couple of lost posts as DNS changes can take a couple of days to propagate -- that means it's possible that some people will be seeing the new host while a handful of others will be seeing the old host (other than not moving hosts, there's not a lot we can do about that).
If people are concerned about the possibility of having two forums up and running while the DNS changes propagate, we can disable the forum on the old host so that only the new host has a working forum. I'll leave that call up to you guys.
Just FYI, someone mentioned using the r65.org redirect to get to the forum earlier. That redirect should still work after the move is made.