What does it mean when I add a new variable to my linear model and the R^2 stays the same? I'm inclined to think that the new variable is not correlated to the response. But could the new variable be correlated to another variable in the model? 
 A: Seeing little to no change in $R^2$ when you add a variable to a linear model means that the variable has little to no additional explanatory power to the response over what is already in your model. As you note, this can be either because it tells you almost nothing about the response or it explains the same variation in the response as the variables already in the model. 
A: As others have alluded, seeing no change in $R^2$ when you add a variable to your regression is unusual. In finite samples, this should only happen when your new variable is a linear combination of variables already present. In this case, most standard regression routines simply exclude that variable from the regression, and your $R^2$ will remain unchanged because the model was effectively unchanged. 
As you notice, this does not mean the variable is unimportant, but rather that you are unable to distinguish its effect from that of the other variables in your model. 
More broadly however, I (and many here at Cross Validated) would caution against using R^2 for model selection and interpretation. What I've discussed above is how the $R^2$ could not change and the variable still be important. Worse yet, the $R^2$ could change somewhat (or even dramatically) when you include an irrelevant variable. Broadly, using $R^2$ for model selection fell out of favor in the 70s, when it was dropped in favor of AIC (and its contemporaries). Today -- a typical statistician would recommend using cross validation (see the site name) for your model selection. 
In general, adding a variable increases $R^2$ -- so using $R^2$ to determine a variables importance is a bit of a wild goose chase. Even when trying to understand simple situations you will end up with a completely absurd collection of variables. 
