Consultas MySQL UNION 2 contendo ORDER BYs

SELECT *
FROM
(
    **(**
        SELECT profileId
        FROM 
        (
            SELECT profileId
            FROM profile profile2
            WHERE profile2.profilePublishDate <= Now()
            ORDER BY profile2.profilePublishDate DESC
            LIMIT 0,40
        ) AS profile1
        ORDER BY RAND()
        LIMIT 0,20
    **)**
    UNION
    (
        SELECT profileId
        FROM profile profile4
        WHERE profileId NOT IN (
            SELECT profileId
            FROM profile profile4
            WHERE profile4.profilePublishDate <= Now()
            ORDER BY profile4.profilePublishDate DESC
            LIMIT 0,40
            )
        ORDER BY RAND()    
        LIMIT 0,40
    )
) TEMP
ORDER BY RAND();

1. cada uma de suas consultas que fazem parte de UNION deve ser colocada entre colchetes (mostrada em negrito para a primeira consulta; a segunda já está dentro)
2. removeu o alias profile3 para sua segunda consulta
3. para o ORDER BY RAND() final , você deve criar o conjunto de resultados UNION para uma tabela derivada; Eu dei TEMP como o alias