Complexity of shortest paths if paths have to use edges from different partitions
If it helps, the problem you are trying to solve is looking for a "rainbow path" between the two vertices.  It's a relatively new area of research, and there's now a book:

Rainbow Connections of Graphs
X. Li and Y. Sun
http://www.springer.com/la/book/9781461431183

Or here's an earlier paper:
G. Chartrand, G. L. Johns, K. A. McKeon, and P. Zhang. Rainbow connection
in graphs. Mathematica Bohemica, 133(1):85–98, 2008.

The result you're looking for is likely in one of those places, something they cite, or something that cites them.