Q:

SVM: Cross Validation Parameter Search Returns Constant Accuracies

I used a parameter search on SVM on a dataset of 469 training examples and 136 features, with labels {1,2,3,4}, using Scikit-Learn.
I expected the results for each SVM implementation to be unique with their respective parameters, but got something different.
The results are the following: for the 'rbf' kernel, the accuracy is constantly at 27.5 %, while the accuracy for the 'poly' kernel is always at 90.8%, regardless of the parameters.
Score: 0.27505330490405117  Parameters: {'C': 1, 'gamma': 0.001, 'kernel': 'rbf'}
Score: 0.27505330490405117  Parameters: {'C': 1, 'gamma': 0.0001, 'kernel': 'rbf'}
Score: 0.27505330490405117  Parameters: {'C': 10, 'gamma': 0.001, 'kernel': 'rbf'}
Score: 0.27505330490405117  Parameters: {'C': 10, 'gamma': 0.0001, 'kernel': 'rbf'}
Score: 0.27505330490405117  Parameters: {'C': 100, 'gamma': 0.001, 'kernel': 'rbf'}
Score: 0.27505330490405117  Parameters: {'C': 100, 'gamma': 0.0001, 'kernel': 'rbf'}
Score: 0.27505330490405117  Parameters: {'C': 1000, 'gamma': 0.001, 'kernel': 'rbf'}
Score: 0.27505330490405117  Parameters: {'C': 1000, 'gamma': 0.0001, 'kernel': 'rbf'}
Score: 0.908315565031983    Parameters: {'C': 1, 'gamma': 0.001, 'kernel': 'poly'}
Score: 0.908315565031983    Parameters: {'C': 1, 'gamma': 0.0001, 'kernel': 'poly'}
Score: 0.908315565031983    Parameters: {'C': 10, 'gamma': 0.001, 'kernel': 'poly'}
Score: 0.908315565031983    Parameters: {'C': 10, 'gamma': 0.0001, 'kernel': 'poly'}
Score: 0.908315565031983    Parameters: {'C': 100, 'gamma': 0.001, 'kernel': 'poly'}
Score: 0.908315565031983    Parameters: {'C': 100, 'gamma': 0.0001, 'kernel': 'poly'}
Score: 0.908315565031983    Parameters: {'C': 1000, 'gamma': 0.001, 'kernel': 'poly'}
Score: 0.908315565031983    Parameters: {'C': 1000, 'gamma': 0.0001, 'kernel': 'poly'}

I have reason to think that the data and their respective labels has to be normalized or worked on. What are possible reasons for the results to behave so?
The code for my parameter search is the following:
tuned_parameters = [{'kernel': ['rbf'], 'gamma': [1e-3, 1e-4],
                     'C': [1, 10, 100, 1000]},
                    {'kernel': ['poly'], 'gamma': [1e-3, 1e-4],
                     'C': [1, 10, 100, 1000]}]
svc = SVC()                    # From Scikit-Learn
clf = GridSearchCV(svc, tuned_parameters)
clf.fit(X_temporary, y_cue_temporary)
means = clf.cv_results_['mean_test_score']
parameters = clf.cv_results_['params']
for mean, param in zip(means, parameters):
    print("Score: {}\tParameters: {}".format(mean, param))

A:

This is probably a consequence of how wide your data is (a lot of features relative to the number of available observations). Alternatively your classes might be very tightly clustered. Or both.
Here's a little toy experiment I built to help you investigate for yourself how the shape of your data impacts GridSearchCV results. I'm basically just playing with the inputs to sklearn.datasets.make_blobs, repeating your gridsearch procedure, and summarizing the GridSearchCV outputs.
NB: This experiment doesn't replicate the difference in performance you observed between the two kernels because I'm generating gaussian clusters. If you want to experiment with simulations that will give you different performance with different kernels, swap out sklearn.datasets.make_blobs in toy_experiment below for a function that produces more exotically shaped. 
import copy
import itertools

import pandas as pd
import numpy as np
from sklearn.model_selection import GridSearchCV
from sklearn.svm import SVC
from sklearn.datasets import make_blobs

from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
import seaborn as sns

np.random.seed(123)

def toy_experiment(data_pars):
    """Performs grid search on data generated subject to the input parameters"""
    default_data_pars = dict(n_samples=300, n_features=3, centers=2, random_state=0, cluster_std=10)
    default_data_pars.update(data_pars)
    X, y = make_blobs(**default_data_pars)

    tuning_pars = [{'kernel': ['rbf'], 'gamma': [1e-3, 1e-4],
                         'C': [1, 10, 100, 1000]},
                        {'kernel': ['poly'], 'gamma': [1e-3, 1e-4],
                         'C': [1, 10, 100, 1000]}]

    return GridSearchCV(SVC(), tuning_pars).fit(X, y)

def search_variance_as_func_of_data_shape(search_pars, verbose=True):
    """
    Runs `toy_experiment` on permutations of arguments provided in search_pars.
    Summarizes each experiment by extracting the mean_test_score from GridSearchCV,
    and reporting the variance and count of unique values in mean_test_score.
    """
    results = []
    arg_names = search_pars.keys()
    candidate_vals = search_pars.values()
    candidates = itertools.product(*candidate_vals)
    for candidate in candidates:
        data_pars = {k:v for k,v in zip(arg_names, candidate)}
        scores = toy_experiment(data_pars).cv_results_['mean_test_score']
        data_pars['n_unq'] = len(np.unique(scores))
        data_pars['var'] = np.var(scores)
        results.append(data_pars)
        if verbose:
            print(data_pars)
    return pd.DataFrame(results)

def surface_plot(df, x, y, z, title):
    fig = plt.figure()
    ax = fig.gca(projection='3d')
    ax.plot_trisurf(df[x], df[y], df[z], cmap=plt.cm.viridis, linewidth=0.2)
    plt.title(title)
    plt.show()

By playing with n_samples (ranging from 100-1000) in addition to cluster_std (ranging from .1-10), we can see that the number of observations doesn't have much impact on the phenomenon you're observing (the small number CV scores from GridSearchCV) relative to the impact of the spread of the data. 
cluster_std_candidates = np.concatenate([np.linspace(0.1, 0.9, 9), np.linspace(1, 10, 10)])
search_pars = {'cluster_std':cluster_std_candidates, 'n_samples':[100, 300, 500, 1000]}
df = search_variance_as_func_of_data_shape(search_pars)
df2 = df[df['cluster_std']<2]

surface_plot(df,  'n_samples', 'cluster_std', 'n_unq', "Unique CV accuracies")
surface_plot(df2, 'n_samples', 'cluster_std', 'n_unq', "Unique CV accuracies, 0<cluster_std<=1")

(sorry for not labeling axes here)

If we look at the variance of the score, we can see two reasons why GridSearchCV might have trouble distinguishing different model candidates (i.e. we observe low variance of CV scores): on the one hand, we have the situation you are observing where the data is tightly clustered and the classifier gives basically the same results regardless what parameters we use. On the other hand, we see the score variances collapses when we turn up the cluster variance because "garbage in, garbage out": the classes just aren't separable, so no matter what model parameters we try we're going to get low accuracy.
surface_plot(df,  'n_samples', 'cluster_std', 'var',   "CV score variance")
surface_plot(df2, 'n_samples', 'cluster_std', 'var',   "CV score variance, 0<cluster_std<=1")

Finally, let's investigate the impact the width of your data has. holding n_samples fixed at 300, varying cluster_std from [.1 to 10] as before, and varying n_features from [3, 100]:
search_pars = {'cluster_std':cluster_std_candidates, 'n_samples':[300], 'n_features':[3, 10, 50, 100]}
df3 = search_variance_as_func_of_data_shape(search_pars)

surface_plot(df3, 'n_features', 'cluster_std', 'n_unq', "Unique CV vs. n_features")
surface_plot(df3, 'n_features', 'cluster_std', 'var',   "CV score variance")

What you're seeing here is a manifestation of The Curse of Dimensionality. Basically, when we add features, the space we're representing our data in becomes increasingly sparse such that even when we have a lot of variance in our clusters, the data is still plenty separable because the clusters can occupy large regions of the feature space without overlapping. 
Before when we held the number of features fixed and cranked up the cluster variance, we observed the varaince of CV scores collapse because our models had nothing to work with. This time, we're seeing the variance collapse because -- once again -- regardless what hyperparameters we use we're going to end up with pretty accurate models and a small number of unique CV scores.

