Linear kernel in SVM performing much worse than RBF or Poly
This depends very much on your dataset: There is data, which can not be separated using a linear kernel. It is impossible, and you won't get any reasonable result. Take for example the simple XOR function. The plot of the XOR looks like this:



No matter how hard you try, you will never be able to separate this using a linear SVM, or any linear method. 

Here's some short MATLAB code which illustrates the problem:

x = [0 0; 0 1; 1 0; 1 1];    % training points
y = [0; 1; 1; 0];            % target: XOR
linearSvm = fitcsvm(x,y);    % train with linear kernel
linearSvm.predict(x)

&gt;&gt; ans = 
        0
        0
        0
        0


The SVM has no chance of finding a solution. Now if we use a kernel, we create a mapping to a higher-dimensional space. The kernel trick allows us to implicitly do this mapping, by calculating a kernel function, which returns the result of a scalar product in this high-dimensional space, without needing to map the input values to this space. The RBF kernel is special, as it corresponds to an infinite-dimensional space. 
Now if we specify a RBF kernel and run the same example again, then:

gaussSvm = fitcsvm(x,y,'KernelFunction','rbf');  % RBF kernel
gaussSvm.predict(x)

&gt;&gt; ans = 
        0
        1
        1
        0


the SVM easily finds the correct result. The same result (in this XOR case) is also found when using a polynomial kernel. There are many more examples, where data simply can't be separated linearly, for example:



Of course, if your data is almost linearly separable, then you can (and probably will) get good results with a linear kernel. Using soft-margin SVMs, which allow for a few misclassifications, often leads to good results, as they can ignore outliers. 

If the linear kernel gives no result, you will have to accept that your data is not (well) linearly separable. You'll either have to switch to a kernel, or allow for more misclassifications in the soft-margin SVM.