I don't think it's really a good critique of a logic problem to say, "but if you remove this extremely important part, it doesn't work anymore"!
The conversation would need to be:
Bernard: I don't know when Cheryl's birthday is
Albert: I don't know when Cheryl's birthday is, and I knew that Bernard didn't know.
Bernard: Then I know when Cheryl's birthday is now.
Albert: Then I also know when Cheryl's birthday is.
Then it works. You only have to assume that the parties are logical and tell the truth.