Does there exist polytime algorithm for this partitioning problem?
(This is about the problem in which $|\phi(\Phi^{-1}(i))|\geq 2$ instead of $|\Phi(\phi^{-1}(i))|\geq 2$. Read it too fast. On the bright side Dave fixes it in a comment to this message )

What about saying it computes a proper edge coloring of a regular graph ? This problem is NP-Complete, and amounts, given a graph as an entry, to find a partition of its edges into matchings.

Vizing's theorem says that to do that Delta (the maximum degree of your graph) or Delta + 1 colors are required, though deciding which is NP-hard.

In your case, I think setting $N$ to the be number of edges, and setting K to Delta would do the trick. You then want to split your $N$ edges into $K=\Delta$ classes, and N is a multiple of Delta (for example in 3-regular graphs, for which the problem is still NP-hard).

In order to ensure that the answer is a proper edge coloring, one can let $\phi_v$ (for each vertex $v$) be the function equal to $0$ when edge $e\in [N]$ is adjacent to $v$, and 1 otherwise. If each color class has at least two different images for each $\phi_v$, it means that each color class contains a edge incident to each vertex. As the graph is Delta-regular, it also means that all the edges around a vertex have different colors as there are only Delta edges around each vertex, and if a class had two it means one would have none.

If it's true it would mean that finding one answer to your question is hard, and sampling solutions too :-)

Nathann