The religion skill in dark sun is not useless if you look at it from a different angle.
History is a more generalized skill so it is less likely that you would have a character that studied history know about the old religious objects that are still around even though the gods are not.
Ex. the party is in a dungeon that a use to be a temple to [insert god here] and have come to a door that is only activated by answering specific questions about the deity or how that religion viewed history, this would make the history check for the challenge much harder then a religion check.
There are other ways to use the religion skill as a main skill in challenges or for interpreting religious texts on the walls of old tombs and such to help get to or around things. Remember that jest because the gods are gone now dose not mean they were never there. Religious cults and peoples are known for there odd ways, intricate religious objects, and mysterious places.
That is jest my take on the matter bass line is that you are the DM do what you fell is best for your campaign and group, a finale thought if one of your players has taken the religion skill try to let him use it every so often to make him or her fell like they didn't waste a skill slot.