Here are two possible interpretations that indicate what the sentences could be taken to mean.
(A) They are capable of solving many more complex problems compared to other birds, such as chickens.
This means that they are capable of solving many more problems that are complex.
It's referring to quantity, not quality:
(A) They can solve more problems of a complex nature than other birds.
Note that it could also be referring to a combination of quantity and quality:
Then can solve a lot of problems of a more complex nature compared to other birds (who can only solve a few).
This is similar to the following interpretation, but subtly different.
(B) They are capable of solving much more complex problems compared to other birds, such as chickens.
This means that they are capable of solving problems that are much more complex.
It's referring to quality, not quantity:
(B) They can solve problems of a more complex nature than other birds.