A Virtual Private Server is a virtual server, provisioned on a larger physical server. You run your own OS and can make any changes you want, without it affecting the host server, or other VPS's on the machine.
The benefit is much larger resources (depending upon the plan you choose), control, and security.
The downfall is there is still the single point of failure. If the VPS or the physical server goes down, your site is completely offline. Most reputable web hosts use things like RAID drives, dual power supplies, etc, but a failure can still happen.
Cloud computing is when your services are spread across several physical resources. This way if one piece of physical hardware fails, others will puck up the load and your services stay online.
A Private cloud marry's the two together so that you have the best of both worlds.
Benefit is, you can have almost 100% uptime of cloud computing, and the security/performance/control of a VPS.
There are still downfalls. If done correctly, this is a rather expensive option. A VPS gives you dedicated resources. A private cloud spreads those dedicated resources across multiple physical servers. This obviously ads to the price.
"Cloud" can also have different definitions depending upon who you ask. Some companies provide truly cloud services, others will have a VPS synced with another VPS behind a load balancer and call it cloud. Make sure you ask questions and are getting what you pay for!
IMHO, If I was looking for a High Availability solution to give high uptime, I would not go with a private cloud. Get 2+ VPS's from different providers, in different data centers, in geographically diverse location. Set roundrobin DNS or use a 3rd party DNS service that offers GSLB. This way, you have your site in multiple locations (protects against complete data center failure and can server your site from the closest DC) and are even protected in case your hosting provider goes out of business and shuts down over night.
A virtual private server is generally hosted at an off-site, third-party web hosting provider. A private cloud is situated on site or at a data center you own. A virtual private server is a single physical server, split up between a limited numbers of users. A private cloud uses distributed resources across multiple physical servers.
A Virtual Private Server has one public IP and each server runs on itself. A private cloud has IPs in a private IP range and only can be accessed if you are on the same IP range or you have a VPN or public access. Private clouds are a group of servers, all for the same purpose or customer, usually under a load balancer, a firewall and security meassures. Only those that need public access from internet will have a public IP.
I think the OP actually confused himself in the wording and the first two replies followed it without considering it is techinically wrong just because they are talking about "private cloud" when it should be a "Virtual Private Server on the cloud" I would say. But their definitions are correct, on the cloud means that resources are distributed from a lot of physical servers, usually giving the advantage if one of them fails the others take over to continue providing reliable uptime while the problem is resolved.