Well, yes, indeed. It depends on the purpose of the abstraction. It may well be that Fly() should not be a method of Bird (maybe we need a FlyingBird subclass, or, even better, a Flying mix-in). My objection was to the "solution" of throwing InvalidOperation, not in support of the assumption that birds can necessarily fly (note the capitalization in may initial remark).
Overall agreed, though. This ties into timr's point that if there are errors in your classifications, then your class hierarchy is incorrect.