New Server and Import Nightmare

My web host moved me to a new server. They said that they would move my accounts, but when I tried to access my blogs I received this error:

Error establishing a database connection

I found that if I changed the location of MySQL in wp-config from localhost to an IP that they provided that I then got an error stating the following:

Can’t select database

I decided to delete the install and start from scratch. I installed WordPress via Fantastico and after it stated that the import was successful, I then navigated to the site. At the site this information is displayed:

WordPress database error: [Unknown column ‘link_count’ in ‘where clause’]
SELECT * FROM wp_categories WHERE cat_ID > 0 AND link_count > 0 ORDER BY cat_name ASC

Also, none of the posts are appearing. Please help. If it helps any, the back-up was from a 2.05 blog and the new blog is 2.1.2