In reply to mountmarcus:
You may be overdoing it, if you've only just started, as your feet aren't used to the strain of supporting your bodyweight using small holds in very thin shoes.
Back off and give it time to build up.
Innersoles won't help - assuming you could even get them in climbing shoes.
If your shoes aren't a good fit, that also won't help and you could possibly try something a bit stiffer to start with - look for "board lasted" rather than "slip lasted" - assuming anything's still made like that, it's been a while since I bought new shoes.