Web-service for wiki-like movie database
A general comment: Extract logic to small private methods. Note that your methods are long which makes it hard to understand what they do. Every independent piece of code should be extracted into a private method. Like 

private void RemoveMovie(id)


If you use the Add method on a List object it will insert the first item into the first place the second to the second and so on. No need in retchanges.Insert(0, new RMovieGenresChange()

GetMovieGenresChanges is a good method since it does only one thing unlike PostMovieGenre method which handles both the addition and the removal of the geners. This is a violation of the Single Responsibility Principle and hence you should split it to two methods: one for the addition AddGenereToMovie and another for the removal - RemoveGenereFromMovie. 
This way yo keep your methods short, clean, readable and maintainable.