Nenhuma das formulações apresentadas pode ser considerada errada, apesar de a expressão "foram avisados de que" ser mais consensual do que a expressão em que se omite a preposição.

Para uma análise desta questão, devemos referir que os exemplos dados estão na voz passiva, mas a estrutura sintáctica do verbo é a mesma do verbo na voz activa, onde, no entanto, é mais fácil observar a estrutura argumental do verbo:

Eles foram avisados do perigo. (voz PASSIVA) = Ele avisou-os do perigo. (voz ACTIVA)
Eles foram avisados de que podia haver perigo. (voz PASSIVA) = Ele avisou-os de que podia haver perigo. (voz ACTIVA)

Trata-se de um verbo bitransitivo, que selecciona um complemento directo ("os", que na voz passiva corresponde ao sujeito "Eles") e um complemento preposicional, neste caso introduzido pela preposição "de" ("do perigo" ou "de que podia haver perigo"). Nas frases em que o complemento preposicional contém uma frase completiva introduzida pela conjunção "que" (ex.: "avisou-os de que" ou "foram avisados de que"), é frequente haver a omissão da preposição "de" (ex.: "avisou-os que" ou "foram avisados que"), mas este facto, apesar de ser muito frequente, é por vezes condenado por alguns puristas da língua.

Bibliografia:
João Malaca CASTELEIRO (dir.), Dicionário Gramatical de Verbos Portugueses, Lisboa: Texto Editores, 2007.
João Andrade PERES e Telmo MÓIA, Áreas Críticas da Língua Portuguesa, Lisboa: Editorial Caminho, 1995, pp. 108-127.

Ver também: regência do verbo precisar, regência do verbo informar (II)

Notas

1. As respostas são datadas e escritas segundo a ortografia da norma europeia anterior ao Acordo Ortográfico de 1990.
2. A base do dicionário foi alterada a 1 de Abril de 2009, pelo que as referências em dúvidas anteriores a esta data podem não corresponder ao conteúdo actual.
3. As respostas sobre questões ortográficas são maioritariamente baseadas na norma ortográfica portuguesa de 1945, contendo as respostas mais recentes indicações sobre a ortografia antes e depois do Acordo Ortográfico de 1990.
4. A bibliografia utilizada está disponível aqui.