The error message in your case is may be correct. First, try to verify that your network path from you to your new server works or not and you can connect with your specified userid/pwd.
1) Open Management Studio and try to connect to your SQL Server instance by the ip address. By this way, you will likely need to use your SQL Server userid/pwd if you dont have already as you are on the Internet host and there are very likely no AD context for the Windows auth.)
2) If you can try to connect to your instance and your database by using the Management Studio then you must have missed the connection string somewhere. So please try to maintain only one location for the said connection string generally in the config file.
I hope it solves your problem.