Hammerfell seceded, and basically got sold out by the empire (read http://www.uesp.net/wiki/Skyrim:The_Great_War). You're definitely on solid ground supporting the Stormcloaks because they want the same things that the redguard already fought for. On my imperial character, I got the Stormcloak quest from a redguard NPC who said "the empire is in shambles, look at all we fought for and they surrendered anyway." There's a http://elderscrolls.wikia.com/wiki/Skyrim on the current situation in Skyrim written by a redguard, and he's very sympathetic to Nords.
People have a superficial, slanted idea of what the Stormcloaks are about, and a lot of nostalgia for the empire that doesn't really fit the current political scene in Tamriel.