I am currently using an SVM with a linear kernel to classify my data.  There is
no error on the training set.  I tried several values for the parameter $C$
($10^{-5}, \dots, 10^2$).  This did not change the error on the test set.

Now I
wonder: is this an error caused by the ruby bindings for libsvm I am using
(rb-libsvm) or is this theoretically explainable?

Should the parameter $C$ always change the performance of the classifier?

The C parameter tells the SVM optimization how much you want to avoid misclassifying each training example.  For large values of C, the optimization will choose a smaller-margin hyperplane if that hyperplane does a better job of getting all the training points classified correctly.  Conversely, a very small value of C will cause the optimizer to look for a larger-margin separating hyperplane, even if that hyperplane misclassifies more points.  For very tiny values of C, you should get misclassified examples, often even if your training data is linearly separable.