You may be right. Although, it seems to me that our group composition seems fine with the exception of the paladin in terms of how it fits with the setting. You don't think so? The race that I think might be from Forgotten Realms might not be. I think it's called Kalashtar? But Tieflings and Humans are specifically detailed in the Setting book.
Edit: And actually, so are the Kalashtar or whatever. They don't get a huge block like humans, but they are mentioned whereas races like gnomes and devas aren't.
The Darksun setting is really a great one, but I think the 4E campaign guide is setting you guys up for failure.
With Darksun, it is a "Sword and Planet" setting, where the alien nature of the world and cultures is a key factor in the enjoyment of the setting. One of the big deals with the setting is that the races are totally different than what you would expect.
Halflings are savage jungle dwelling head hunters and cannibals, with a strong primal bent. They largely live beyond the ringing mountains and are fairly rare in the Tyr region.
Elves are free spirited desert running nomads who are usually borderline sociopaths at best. The entire concept of "being responsible" or "planning ahead" is laughable to them. They are lazy, shiftless, and will do exactly as little work as is required to get by for the day. They are often murderous desert raiders, or back alley criminals. Reserved, cultured, and thoughtful Tolkien like elves would be aghast. Tree hugging earthmother types with mood crystal collection elves would be horrified.
Dwarves pick a goal for their life and will do anything to accomplish it. Anything. If they need to build an orphanage to get it done, so be it. If they need to burn down an orphanage to get it done, so be it.
Thri-Kreen have an alien hive like group psychology, everything is about order and position within the group, and for the benefit of the group. They are also an insectoid species that thinks very differently than humanoids.
Half-giants are not terribly bright, but are keen observers who mimic the cultures, personalities and even ethics of the people around them. If a half-giant is wounded and is left in the care of a healer, they will start to act like a care-giver who helps people. If that same half-giant is captured by a group of slavers and desert raiders, that half-giant will become a raider. Some aspect of their personality will stay fixed though, maybe they are always lawful for example, but good or evil depends on the environment.
Races like Tieflings were inserted into the setting because Wizards was "afraid they would make someone cry if they couldn't play their favorite race from the PHB1". I'm dead serious, it was in one of the seminars about the 4E version.
I think in the end they were just too afraid to "lay down the cannon" for the setting, and gave you a watered down impression of the setting. Since you were new to the setting and didn't know any better, that lead you astray and to the conclusion that things didn't feel "different" enough.
They basically offered to cook you a big plate of Indian food, then they got scared that you might not like the strong spices and made it bland, and now you are "meh" on Indian food because bland food isn't terribly inspiring. Oh, and they added hamburgers to the menu because they were afraid someone might come to an Indian restaurant and not want to order Indian food.
I'd say have everyone re-roll with a "core" Darksun race (Human, Elf, Dwarf, Mul, Thri-Kreen, Half-Giant, Halfling). Have them pick a Martial, Primal, or Psionic power source. Maybe allow one player at most to be an Arcane power source, since defiler/preservers are hunted like dogs in the setting (like straight up, cast a spell on a street and a mob will pick up cobble stones and try and stone you to death), said party member should be afraid to even let the other party members know they are a preserver/defiler for a good long while. Use the inherent bonuses system and the 'non-metal weapons break on a 1' rule. Have the DM embrace his inner "evil cackle", and have fun.