BTC Guild started setting up a new server this morning running modified block rules. Currently trying out a 500,000 byte maxblocksize. The problem is with larger blocks, you increase the chance of orphans since it will take at least twice as long to propagate, if not more. I've modified the fee settings to prefer fee based transactions when increasing the block size past 50 KB, so hopefully the increase in fees per block offset the orphan rate increase.
I'm actually hopeful that you won't notice much difference in propagation times.
We're talking about 500kb data structures here. Any mining pool worth its salt is running out of decent colo facilities in the USA or Europe with good connectivity. Transmission time is negligible at current sizes. The slow part is validation and disk IO. However Bitcoin 0.8 has two features that should make acceptance of a new block fast:
1) The signature cache means that when you see a transaction appear in a block, you are very likely to have already checked its signatures when it was previously broadcast through the memory pool (your node is "warm"), so there's little or no ECDSA computations required.
2) LevelDB means the difficult parts of managing the disk is done on a separate thread. In theory you should need only a handful of disk IOPs to accept a new block because all the compaction is done on a separate core in the background.
I think it should be quite feasible to accept and announce a new block in something like 30-40 msec.
So I'll be very interested to see if practice matches theory - if it does then you should not see a 2x propagation time, certainly not more than 2x. And if you do then we just need to fix it

You're forgetting that every node needs to receive, then process (incl signature checks) each block before it even begins relaying it to its next peers.