I had the same problem with BTCGuild, even though I live in California (where their servers are). Very odd. I haven't had any problems with Deepbit or BTC mine.
When were you having the problem? The server moved to a dedicated server 4 days ago, which has virtually eliminated the issues the old box was having.
This is normally an error from people who are mining from countries with poor connections to a US based server. The lag between you and the server means sometimes if you finish two work units in quick succession, you have not yet received new work from the server (miners keep 1 unit in queue behind the one they're currently working on).
Try running phoenix with -q 3 or -q 4, which will increase the amount of work the client tries to keep stored locally. This has solved the issue for some of the people connecting from countries in Africa, or from China, or people that connect by wifi, 3g/4g, or satellite internet.
Many thanks eleuthria, again you've provided a brilliant answer, that trick worked a treat. Am I right in thinking the BTCguild is yours? If so congratulations on a very impressive pool! Was wondering if you could put up a small one box calculator so we can work out the 24hr payout at certain average speeds, like deepbits pages have. For instance, i input 400 Mhash and get a figure of 1.1 BTC per 24 hours.
This weekend I'll be adding a 24-hour statistic to the pool for keeping track of that, and an added perk for 2% donators where you'll receive an income statement-like report in your email each day (or week) detailing your earnings, withdrawals, and worker stats for the previous 24 hours worth of blocks.