Relationship between the kernel and the value of C in SVM's How exactly does the value of $C$ relate across different kernels that we can use for SVMs? As in, how does it vary when changing the polynomial degree of a kernel or while using a Gaussian kernel?
 A: Try this paper. Your answer might be at chapter 3.2, figures 2 and 3. 
Long story short: The same performance can be obtained for different pairs of C and kernel parameters. You shouldn't try to manually tune a SVM.
Edit: Some details:
I usually tune C (the cost parameter) when I have largely imbalanced classes. That is, one class have 10% and the other 90%. Some SVM libraries (esp. libSVM which I use) lets you specify a cost for each class. According to libsvm paper, $\frac{c_1}{c_2} = \frac{n_2}{n_1}$ where $n_2>n_1$ , $n_i$ is the volume of the i'th class. If you let $c_2 = 1$ then $c_1 = n_2/n_1$ . There is also a "global" C, that is multiplied with the specific $c_i$ values.
When the learning algorithm computes the error for the current SVM parameters, it multiplies each wrongly classified instance with this cost. If the cost is the same for both classes, the lesser class errors will get diluted and your final model will tend not to predict very well (or not at all) the weakly represented class.
Gamma acts as the $\sigma$ for a Gaussian kernel $G(x) = exp(-x^2/2\sigma^2)$. Note from the equation of RBF : $K(x,y)=exp(-\gamma||x-y||^2)$  that $\gamma$ is more or less proportional to $1/\sigma^2$. Basically $\gamma$ controls the width of the kernel.
The intuition behind this is that a large kernel will tend to produce a smoother border between classes and a narrower kernel a more intricate border. In extreme, the former will tend to give higher bias (it learns only the general aspect of the data) and the latter will tend to overfit (it learns all the details, including the outliers and errors in the data). None of these extremes are welcome in applications. A midpoint is desired, but this midpoint cannot be computed analytically and depends on the actual data.
This is why, the metaparameters are usually searched through cross validation. Please keep  in mind that you must optimize for BOTH parameters in the same time.
The cost parameter C.
The theory says that SVM is a large margin classifier. In layman terms this means that it tries to find a border that is somehow as far away as possible from both classes. See the figure below (wikipedia).

Both H2 and H3 are ok, but H3 is better because if new samples arrive, is more likely to be classified wrong by H2 than H3, because H2 crosses near the black group.
The math behind SVM ensures that if a border is found, this is the one gives the largest gap between the data. 
And now the tricky part: In the data you have outliers, errors, etc. basically data that is labeled as white but resides near the black group and vice versa. You have two choices: Move the border so you minimize the number of samples that will be learned wrong OR ignore few samples here and there but ensure that the border gives you large separation between classes. 
The cost parameter C "tunes" the algorithm between better fitting the available data or giving a larger margin. If I'm not mistaken, small C means that you prefer larger margin.
Hope it helps!
p.s. I am not an expert in SVM so I can't give you the intuition on how exactly the values for global cost parameter C actually influences the results or the convergence speed of SVM.
