There are such misconceptions floating around...

OK first mdude77 is wondering why the latency is lowered by restarting bitcoind and raises again.

When you restart bitcoind it doesn't save the list of unconfirmed transactions on disk: they are only maintained in what's called the memory pool.
When you restart it, at first it doesn't have any transaction in its memory pool. So any rpc call to bitcoind involving any parsing of the list of transaction in the memory pool is fast: getblocktemplate is obviously one of them as its goal is to build a template for a block including the tx in your memory pool that your bitcoind deems worth confirming.
Then your bitcoind learns of unconfirmed transactions at the rate at which it's neighboors (the nodes it's connected to) on the bitcoind P2P network transmit them. Only new transactions are automatically broadcasted and received by a freshly started node quickly, old ones are transmitted far slower to avoid network congestion. So a freshly started node gets new transactions appearing on the network quickly and slowly catches up through the backlog of unconfirmed transactions. The rate at which a node receives old transactions varies greatly: it depends on the nodes it is connected to (not every node is configured the same, some may relay more transactions than others).
This is why getblocktemplate latency is slowly rising and is perfectly consistent with getblocktemplate latency being heavily dependent on both the number of transactions your bitcoind accepts in its memory pool and the number of transactions it selects for confirmation (these being controlled by maxblocksize, minxtxfee and minrelaytxfee among others).

Second: the getblocktemplate and P2Pool orphan rate.
First a bit of vocabulary just to avoid any misunderstanding: what daemondazz calls P2Pool blocks are P2Pool shares.

AFAIK P2Pool doesn't need a fresh getblocktemplate to build a share. It can reuse a previous one (unless a Bitcoin block has just been found, then shares based on old templates would generate orphan blocks, see one of my earlier posts on why it's bad). The only drawback of using an old getblocktemplate result is that it doesn't include new transactions that were received after it (so it lowers the fee income and slow transaction confirmation a bit).

What the problem is is probably more subtle than that: P2Pool is an event-driven program (as opposed to multi-threaded or multi-process) with most of its event being handled asynchronously (waiting for a getblocktemplate result is probably done asynchronously).
What could happen but is very difficult to analyze is that the event-driven framework doesn't cope with long running queries as well for some obscure technical reason (like polling some event result in exponentially longer intervals instead of being woken up by a select or equivalent system call) or might have a timing problem when some task that can't be done asynchronously (like pure crypto computations) happens to be done right when the geblocktemplate comes back. There's even a system in place in P2Pool to punish shares computed from old templates when a newer block is known: P2Pool nodes generating them because of high getblocktemplate latency will most probably see them orphaned.

I don't know the exact reason why getblocktemplate affected efficiency and even if it's still the case today as forrestv might have changed something that removes this problem. It was still the case very recently (like less than 2 months ago) when getblocktemplate took more than 0.2s. I don't check often how it affects p2pool but I'm doing it right now (in fact I'm studying how the block size and fee limits affect getblocktemplate in the current situation, checking the efficiency is just a bonus). If the behavior of p2pool changed I'll know it in the following days and will be able to update my guide. For now I still recommend to keep it under 0.2s to be safe.