REST is about resources. If /users/me/contacts
is the URL of a resource (list of contacts), it must always return the full representation of the resource state.
If you want to retrieve only those contacts that have changed, use a query parameter:
/users/me/contacts?newerThan=20130513124300
with newerThan
the date the client last accessed the resource.
This would be RESTful since every different value of newerThan
would form a different URL.