Complexity of shortest paths if paths have to use edges from different partitions

We are given a simple, undirected, weighted, incomplete graph $G=(V,E)$, where $V$ is the set of vertices, and $E$ is the set of edges. In addition, a collection of sets $S$ is given, which fully partitions $E$.

For any two vertices in $V$, I need to find the shortest path between them.
The additional caveat is that no two edges which belong to the same partition may be in the path.

This has totally thwarted any polynomial algorithm I can think of. It confounds algorithms like Djikstra, because at any step during the process, it may be best to forgo the best available edge in favor of having a better choice still open in the future.

I've tried reducing it to the traveling salesman problem, and several others, but I can't quite get there. Proof-writing is not really my strongest suit. Any point towards proving this would be much appreciated.

EDIT: Yes, $S$ is a partitioning of $E$. This does seem to be perfectly analogous to rainbow graphs. Is it known that finding rainbow paths on an unweighted graph is NP-Hard?

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.

StackExchange Computer Science Q#65076, answer score: 2