matches verifica a string inteira. Então se ela tiver um único caractere que não corresponde à expressão, retorna false.
Os colchetes delimitam uma classe de caracteres, então [a-zA-ZÁÂÃÀÇÉÊÍÓÔÕÚÜáâãàçéêíóôõúü] procura por uma letra de “a” a “z” (indicado pelo intervalo a-z), ou uma letra de “A” a “Z” (A-Z), ou a letra “Á”, ou a letra “”, etc (qualquer uma delas serve).
Já o asterisco é um quantificador que significa “zero ou mais ocorrências”, portanto essa regex pega zero ou mais letras (qualquer uma das letras que estão dentro dos colchetes). Por isso que quando tem um espaço ela retorna false, pois a regex não diz que é para considerar espaços.
Vale lembrar também que, como o * significa “zero ou mais ocorrências”, então essa regex também retorna true se a string for vazia (""). Então se quer forçar que tenha pelo menos um caractere, pode trocá-lo para + (que significa “uma ou mais ocorrências”).
Para forçar que tenha um espaço, pode trocar para:
if (nome_recebido.matches("[a-zA-ZÁÂÃÀÇÉÊÍÓÔÕÚÜáâãàçéêíóôõúü]+( [a-zA-ZÁÂÃÀÇÉÊÍÓÔÕÚÜáâãàçéêíóôõúü]+)*")) {
Ou seja, primeiro tem uma ou mais letras. Depois tem um espaço seguido de uma ou mais letras, e todo este trecho (espaço + letras) pode se repetir zero ou mais vezes (repare que todo este trecho está entre parênteses e seguido do *, o que indica que “zero ou mais ocorrências” se aplica a tudo que está nos parênteses, que no caso é o “espaço + letras”).
Isso pode ser simplificado para:
if (nome_recebido.matches("\\p{IsLatin}+( \\p{IsLatin}+)*")) {
Agora usei o Unicode Property Escape \p{IsLatin}, que pega as letras do script Latin (o que inclui as letras acentuadas, tanto maiúsculas quanto minúsculas). A lógica é a mesma da anterior: uma ou mais letras, seguida de espaço + letras (e o trecho “espaço + letras” pode se repetir zero ou mais vezes).
Outro detalhe é que matches cria uma nova regex a cada execução, o que pode não parecer, mas é uma operação bem custosa (pois toda regex precisa ser compilada e possui um overhead que você não vê, mas está lá).
Se forem feitas muitas verificações, o melhor é compilar a expressão apenas uma vez e reusá-la. Para isso você pode usar estas classes:
import java.util.regex.Matcher;
import java.util.regex.Pattern;
E o código ficaria assim:
// criar as regex apenas uma vez
Matcher letras = Pattern.compile("\\p{IsLatin}+( \\p{IsLatin}+)*").matcher("");
Matcher digitos = Pattern.compile("[0-9]+").matcher("");
// usar com uma string
String nomeRecebido = "Paula Luíza";
if (letras.reset(nomeRecebido).matches()) {
System.out.println("Só tem letras.");
} else if (digitos.reset(nomeRecebido).matches()) {
System.out.println("Só tem dígitos.");
}
// reaproveitar a regex com outra string
String outroNome = "Fulano de tal";
if (letras.reset(outroNome).matches()) {
System.out.println("Só tem letras.");
} else if (digitos.reset(outroNome).matches()) {
System.out.println("Só tem dígitos.");
}
Também mudei o nome da variável para ficar aderente às convenções de nomenclatura da linguagem, pois no Java há a preferência por nomesDesseJeito em vez de nomes_desse_jeito.