A principal diferença é a rota para 0.0.0.0/0 na tabela de rotas associada.
Uma sub-rede privada define essa rota para uma instância do NAT. Instâncias privadas de sub-rede só precisam de um ip privado e o tráfego da Internet é roteado através do NAT na sub-rede pública. Você também pode não ter nenhuma rota para 0.0.0.0/0 para torná-la uma sub-rede verdadeiramente privada sem acesso ou saída à Internet.
Uma sub-rede pública direciona 0.0.0.0/0 por meio de um Gateway da Internet (igw). Instâncias em uma sub-rede pública exigem que os IPs públicos falem com a Internet.
O aviso aparece mesmo para sub-redes particulares, mas a instância só é acessível dentro do seu vpc.