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.
From this guide: