The issue you're seeing may be related to the wobbly condition of the servers at the minute. Niantic have tweeted (on the Pokemon Go News account) that they advise against using valuable consumables (lucky eggs, incense etc) before the servers are stable.
My advice would be to not use incense while you have the spinning white "loading" pokeball symbol on the top left hand part of your screen. If this wasn't the case when you used it and the issue persists then it might be a separate issue that I'm unaware of.
As a temporary work-around, try heading somewhere busy. I read somewhere that pokemon are more common in densely populated areas like city centres, though I haven't tested this yet. My personal experience is that I'm more likely to find pokemon near water and playing the app while on the train usually results in an encounter every other station or so.
Edit: Ok, pokemon are almost certainly more common in busier places. I rode a bus 20 minutes from the town centre to a suburb and the encounter rate dropped the further out I got.