"Paella" in the US (and much of non-mediterranean Europe) generally implies shellfish. This is only common in some parts of Spain, and is not considered an 'authentic' Valencian paella.

An American would absolutely recognize it for what it is, it might just be a bit different from what they where assuming.

That being said most Spaniards happily chuck whatever they happen to have laying round into their paella when cooking at home.