We have a very similar problem with them, as we do with you. We allow Americans in without visas--all of us. They do not allow all of us in without visas. Your list of our member states where visas are required is the three Baltic republics, so Estonia, Lithuania, and Latvia, the Czech Republic, Slovakia, Hungary, and Poland. They have that list, to which they have added Greece--not even a new member state, as Greece has been a member state for a long time--Malta, and Cypress, for reasons that are not altogether clear.
On May 17th, 2006. See this statement in context.