Well, you'll have to provide a little more info from your previous host.
1. What version of UBB are you using?
2. How much bandwidth were you previously/currently using?
3. How much hard drive space are you using?
4. What kind of server were you on previously.
Number 4 above can tell us a lot. If your previous host had an "ultimate" server then you probably need a dedicated server.
Which brings me to my last question, are you looking at shared server solutions or dedicated server solutions?