When users interact with a voice-operated service, they bring along their habits as well as their expectations from experience with human-human dialogues, with the domain, and with other systems and services. In addition, users' expectations are further shaped while using a system. The present study explores the extent to which user-system interaction, and in particular difficulties in the interaction, are affected by users' expectations and (mis)conceptions of the service, and how these expectations evolve during use. In an exploratory study, twenty subjects queried two different train travel information services. A semi-structured interview was held on subjects' dialogues with the systems, by replaying the recordings together with the subjects. In interacting with voice-operated services, users appear to draw from various sources of experience. Users' misconceptions and misunderstandings of the system lead to various problems in interaction, such as undesired travel suggestions and irritation. The implications for the design of voice-operated services are discussed.