A records control how your nameservers translate a domain name into one or more IP addresses, eg. example.com -> 208.77.188.166
It's unusual to get the bounces you describe after just changing a single A record, but not impossible - it might be for example that your ISP runs two resolvers and only one's been updated, so you get a different answer depending on which you connect to.
A much more common cause though is misconfigured dns. Try your domain at
www.intodns.com and see what it says.
Edit: It could be that they've added a new A record pointing to the new server in addition to the earlier one pointing to the VPS - having 2 A records for your site would give exactly the behaviour you're describing...