Set Cover for Permutation Matrices
Over lunch in Brussels we proved this problem is NP-Hard by a fairly short reduction from 3SAT. Our proof doesn't lead to an inapproximability result (yet). We'll think more about it.

Roughly, you transform a 3-SAT instance (with n variables and c clauses) into a series of permutations structured as follows:

1...n for numbering the n variables
n+1 used by the variable gadget
n+2, n+3 representing the 1st clause
...
n+2j, n+2j+1 representing the jth clause
n+2c+2 used by the garbage collector

variable xi is represented by the permutation
1,...,i-1,n+1,i+1,...,n,i,...
and swapping n+2j+1, n+2j for every clause where j where xi appears;
and  the permutation
1,...,i-1,n+1,i+1,...,n,i,...
and swapping n+2j+1, n+2j for every clause where j where -xi appears.

Then we use the garbage collector to place each number in a position where it could not appear otherwise. To place x in position y, we put y in position n+2c+2 and n+2c+2 in position x. We will have exactly n+2c-1 such garbage collectors for each variable and 2(n+2c-1) for each clause. The 3SAT is satisfiable iff we can choose exactly one of the 2 permutations for each variable, iff the permutation set cover has a solution of size n+(n+2c-1)(n+2c).

There are probably some minor details missing for small instances.

Stefan.