Difference between OData and REST web services
The OData protocol is built on top of the AtomPub protocol. The AtomPub protocol is one of the best examples of REST API design. So, in a sense you are right - the OData is just another REST API and each OData implementation is a REST-ful web service.
The difference is that OData is a specific protocol; REST is architecture style and design pattern.
UPDATE Warning, this answer is extremely out of date now that OData V4 is available.
I wrote a post on the subject a while ago here.
As Franci said, OData is based on Atom Pub. However, they have layered some functionality on top and unfortunately have ignored some of the REST constraints in the process.
The querying capability of an OData service requires you to construct URIs based on information that is not available, or linked to in the response. It is what REST people call out-of-band information and introduces hidden coupling between the client and server.
The other coupling that is introduced is through the use of EDMX metadata to define the properties contained in the entry content. This metadata can be discovered at a fixed endpoint called $metadata. Again, the client needs to know this in advance, it cannot be discovered.
Unfortunately, Microsoft did not see fit to create media types to describe these key pieces of data, so any OData client has to make a bunch of assumptions about the service that it is talking to and the data it is receiving.