I have an object that flies in circles using Bezier Circle curve modifier. I would like to add rotation to the Bezier Circle itself. But once I'm trying to animate the Bezier Circle spin, the object doesn't follow the circle's path, but it just flies away.
The following animation shows what I think you are asking for.
(i) keyframe the curve using the key-shorcuts i then t while the timeline slider is at the beginning of the animation sequence.
(ii) Add another object and move it to the edge of the curve.
(iii) Now, with the model selected, hold shift and select the curve. This should leave the model outlined in orange, indicating a secondary selection with the curve highlighted with yellow(the primary selection).
(iv) Use ctrl+p and select->Follow Path (several options work for this, I'm not sure what the subtleties are for the various types ;)
(v) now you should be able to move the curve around and keyframe its different transforms along the timeline.
Where the object and curve are, in relation to each other, when you parent them will be affected by where the timeline slider is when you parent the objects. Here is an animation that shows what happens when I parented the model to the curve mid-way through the animation.