Mas até agora não consegui entender que 'problemas' eles resolvem. Pra mim parece que são problemas relacionados a orientação a objetos ou não são nem problemas de verdade.
No caso do livro do GoF os problemas que eles resolvem estão descritos nas primeiras seções de cada padrão: Intenção, Motivação e Aplicabilidade.
E são vários padrões, qual deles você não entendeu o problema que ele resolve? Talvez tenha pouca vivência no desenvolvimento OO e não tenha se deparado com eles.
Pra mim parece que são problemas relacionados a orientação a objetos
Sim, a proposta do livro é essa. É possível que existam padrões documentados para outros paradgimas como o funcional e procedural, mas se estamos discutindo sobre os padrões do livro do GoF os problemas ali são os que surgem quando se programa com orientação a objetos.
Se você não entende ou não usa orientação a objetos, de fato os padrões não servem para você. Da mesma forma que se você não pilota aviões não faz sentido entender e aplicar as regras de tráfego áereo.