Core Data model of video and entities
Perhaps I'm missing something, but it seems that the Video objects don't really need to know about what playlists they belong to, do they?

A playlist is a collection of videos.  You don't need a playlist index object.  You just need an array on each playlist that keeps track of what videos are on its playlist and in what order.  A simple array does all this for you.

It seems to me that the only reason a video would need to know what playlists it belonged to is if you wanted to provide some functionality for a video to quickly find all playlists it belonged to.  And when I say this, I mean a request where it's important for this information to be returned near instantly.

Even without the video knowing any information about the playlists, your code could still iterate through every playlist asking it whether or not it contained a given video and get the answer to what all playlists the video belongs to.  This might be a little time consuming, but I think it's a rare request.

But it seems what's most likely is that a user will either want to play an individual video, or play a playlist.  The request to play all playlists that contain this particular video seems an odd one to me.