I think the 512 difficulty is too much for CPU mining. I ran cpuminer on 3 cores of my machine (33 kh/s total) and got work submitted after 21 mins.
You may want to look at mining Primecoin (XPM). This is where I put my CPU to work:
http://www.peercointalk.org/index.php?topic=485.0This simply isn't true. CPU mining is perfectly viable at 512 share difficulty. Share difficulty DOES NOT MATTER - it only increases variance.
It sounds to me like his stratum proxy is lagging - try pointing the miners direct to the pool and see what happens.