What the OP did not say is if he called the hotel in advance to ask what their early check-in policy was and/or to request an early check-in. If I have any special request for a hotel, I will call them in advance, to know what I can expect.
Although I think that it is cheap of the hotel to charge an early check-in fee if a room is ready, I also think that it is pretty poor planning to show up eight or nine hours before check-in time, then just assume that things will work out.