We are currently investigating the use of rhythm and synchrony in human-robot interaction. Specifically, we are developing techniques for the perception and generation of social rhythmic behaviors in nonverbal dance-oriented play between children and a small creature-like robot. While our goal is to develop and evaluate technological artifacts that can participate in rhythmically coordinated social interactions, it is first necessary to develop and evaluate appropriate methodologies for the evaluation of such technology. In this paper we present our experience in developing and revising an experimental paradigm for the evaluation of dance-oriented play with a robot. We propose that strictly controlled experimental paradigms for even such constrained interactions preclude the full expression (and therefore observation) of interactive behaviors that can be considered sufficiently rich and natural for the study of the complex yet fundamental rhythmic properties of social interaction.