Just got the Gods and Kings expansion and was playing 3 player game with friends. They both made a religion and I was over 1000 in faith and still could not work out how to create a religion or get a Great Prophet.
How do you create a religion?
There are two steps:
First, when your Faith reaches a certain level you can found a Pantheon. However, every time someone founds a Pantheon, the threshold to found the next one goes up.
Next, when your Faith reaches another threshold you'll get a Great Prophet - from what I can tell this will only happen if you've got a Pantheon, though. You can then use the Great Prophet to create your full religion.
There's one wrinkle, too: only a certain number of religions can exist so if they've all been founded already (by your friends or CPUs) you won't be able to found one.
I'll try to edit in the actual numbers if I can find them.