Consulta SQL complexa com várias tabelas e relações

Acredito que esta consulta fará o que você deseja:

SELECT array_agg(players), player_teams
FROM (
  SELECT DISTINCT t1.t1player AS players, t1.player_teams
  FROM (
    SELECT
      p.playerid AS t1id,
      concat(p.playerid,':', p.playername, ' ') AS t1player,
      array_agg(pl.teamid ORDER BY pl.teamid) AS player_teams
    FROM player p
    LEFT JOIN plays pl ON p.playerid = pl.playerid
    GROUP BY p.playerid, p.playername
  ) t1
INNER JOIN (
  SELECT
    p.playerid AS t2id,
    array_agg(pl.teamid ORDER BY pl.teamid) AS player_teams
  FROM player p
  LEFT JOIN plays pl ON p.playerid = pl.playerid
  GROUP BY p.playerid, p.playername
) t2 ON t1.player_teams=t2.player_teams AND t1.t1id <> t2.t2id
) innerQuery
GROUP BY player_teams

Result:
PLAYERS               PLAYER_TEAMS
2:Allen,3:Pierce      1,3
4:Garnett,5:Perkins

Ele usa array_agg sobre o teamid para cada jogador em plays para combinar jogadores com exatamente a mesma configuração de equipe. Incluí uma coluna com as equipes por exemplo, mas que pode ser removida sem afetar os resultados desde que não seja removida do grupo por cláusula.

Exemplo do SQL Fiddle. Testado com Postgesql 9.2.4

EDIT:Corrigido um erro que duplicava linhas.