I wonder whether long polling doesn't work for me. I've got a rather high stale ratio (about 4-5%) and there're always a few rejected shares reported by phoenix just about the time there's a new block solved on DeepBit.
I've noticed the same, and I'm using phoenix too. It only happens after mining for some time. Looks like phoenix loses the LP connection after a few hours. After restarting, phoenix will show "[24/05/2011 15:09:01] LP: New work pushed" correctly.
Still, the phatk kernel provides a much better hash rate for me, so I just restart phoenix when I notice that there has been no LP for a long time.