Consulta SQL compleja con múltiples tablas y relaciones

Creo que esta consulta hará lo que quieras:

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

Utiliza array_agg sobre el teamid para cada jugador en plays para emparejar jugadores con exactamente la misma configuración de equipo. Incluí una columna con los equipos, por ejemplo, pero eso se puede eliminar sin afectar los resultados siempre que no se elimine de la cláusula group by.

Ejemplo de SQL Fiddle. Probado con Postgesql 9.2.4

EDITAR:se corrigió un error que duplicaba las filas.