This is what I was told in high school theology class:
Originally, Catholics were not allowed to eat fish during Lent, either, but the Catholic pope who changed the rule had a brother whose fishing business dropped off entirely during the Lenten season. He changed the rule to help his brother out financially.
The official word from the Catholic sources is that fish is separated from other meat because it comes from the water. Some people eat birds, too, because they somehow got the idea that birds also sprang from the water (?).