I know you have to go to a major city to replentish your essence, but when I go it doesnt seem to work. Is there something special I have to do, or do I simply have to wait?

Your essence wont replenish in towns or from essence pools if you have still have creations as your essence is used to sustain them.

You have a finite amount of essence.

As DCT says, if you have creations then they will account for a certain amount of your essence. The more creations you have the less essence you will have left for spells. When you get to a town the essence fills up very quickly.