How long has the site been on this VPS, and how long ago was the domain registered? If it's only recently, it may just be propagation issues. If the above DNSreport doesn't show any major problems, and the site/domain has been there for a while, it could just be the route to the server.
However many other users cannot reach the server at all. via Domain or via IP.
They get the server not available,etc.
There isn't even a connection attempt logged.
It's unlikely to be propagation then. Not reaching via domain or IP suggest routing issues, either at the server or somewhere in route (more likely). If you can reach it, and they can't it's probably in their path to your server (ISP, hops along the way, etc). A smaller chance is that a firewall has blocked them at the server level...if you're running one.
Not logging a connection attempt is logical, if they can't reach the server...
I'd guess it's routing, but not locally. If you can get the users to do a traceroute to your server when they can't reach it, there might be a clue in there.