Nested query efficiency in MySQL
Add indexes on (attribute, id2) and on (id2, attribute) and try this:

SELECT
    m.atttribute,
    COUNT(*) AS cnt
FROM 
    mytable AS m
  JOIN mytable AS m1
    ON  m1.attribute = 'blue'
    AND m1.id2 = m.id2
  JOIN mytable AS m2
    ON  m2.attribute = 'red'
    AND m2.id2 = m.id2
GROUP BY
    m.attribute
HAVING
    m.attribute NOT IN ('blue', 'red') 
ORDER BY
    cnt DESC ;


Test in SQL-Fiddle