What exactly is the "paradox" in Olber's Paradox?
Olber's Paradox was created at a time before the idea of a finite universe was accepted.  (It was thought of in the 1600's).  In order to resolve Olber's Paradox, you have to introduce the idea that either the universe had a beginning or it is of finite size.  (Note: the solution does not require an expanding universe).  So, at the time, it was a paradox.  Pretty much all astronomers considered the universe to be static and infinite.  Therefore, the fact that their observations didn't fit with what they expected made it a paradox.