A records control how your nameservers translate a domain name into one or more IP addresses, eg. example.com -> 22.214.171.124
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...