We investigate the effectiveness of several types of virtual fixtures in a robot programming by demonstration interface. We show that while all types of virtual fixtures examined yield a significant reduction in the number of errors in tight tolerance peg-in-hole tasks, color and sound fixtures generally outperform a tactile fixture in terms of both execution time of successful trials and error rate. We have found also that when users perceive that the task is very difficult but the system is providing some help by means of a virtual fixture, they tend to spend more time trying to achieve a successful task execution. Thus, for difficult tasks the benefits of virtual fixturing are better reflected in a reduction of the error rate than in a decreased execution time. We conjecture that these trends are related to the limitations of currently available interfaces for human-robot interaction through virtual environments and to the different strategies adopted by the users to cope with such limitations in high-accuracy tasks.