It occurs to me that alot of the problems with religion derive from the fact that the religions in EU2 (which also represent a big chunk of the culture of a country) are inflexible, and do not change in the course of a game, whereas in history there were often pretty large shifts in culture and belief (particularly thinking of China here).
Maybe we could fix this by changing the way religions work. Get rid of Budhist and confusian for instance and replace them with "active Budhism" and "stagnat Budhism" (or some more appropriate name). States across the present Budhist Confusian range would then shift between the two. For example, China would start with the "active" religion, but when the withdraw into themselves, they would convert to the "stagnant" religion. Etc. etc. so on and suchlike.
Paganism and Hinduism could be similarly changed into "animism" and "advanced panthesim". However, because of hardcoded effects, Shia and Sunni might be a bit more difficult to fit into this idea, but then again they don't have as much need to, so we could keep them as they are.