The presence of the "when" clause doesn't really change anything. It's as you said in your first sentence. If the time that you saw the movie together is before another past time that you've referred to, then use "had seen".
New words, one handy idiom, and a 2-minute quiz — delivered to your inbox to keep your streak alive.