How to deal with time series which change in seasonality or other patterns?
After reading your question, I became curious about the topic of time series clustering and dynamic time warping (DTW). So, I have performed a limited search and came up with basic understanding (for me) and the following set of IMHO relevant references (for you). I hope that you'll find this useful, but keep in mind that I have intentionally skipped research papers, as I was more interested in practical aspects of the topic.
Resources:

UCR Time Series Classification/Clustering: main page, software page and corresponding paper
Time Series Classification and Clustering with Python: a blog post and an ipython notebook
Capital Bikeshare: Time Series Clustering: another blog post
Dynamic Time Warping using rpy and Python: another blog post
Mining Time-series with Trillions of Points: Dynamic Time Warping at Scale: another blog post
Time Series Analysis and Mining in R (to add R to the mix): yet another blog post
And, finally, two tools implementing/supporting DTW, to top it off: R package and Python module