Well, I spoke with him ( earthmark ) and another coder that just happens to be my roomate ( 015r ) and they kept discussing a few different points. Without going into crazy detail and boring all of you, the problem is that octree's are rather large. When a player modifies a block the node that the octree is associated with has to be sent. If our estimates are correct this is close to 44kb being sent just for the octree alone.
One aspect of octrees is that they don't change too much if you delete a single block inside them. You should be able to just send the difference between the old and new octree (probably just a leaf is gone, perhaps one node that becomes a leaf, or perhaps two nodes are changed, and so on with lower and lower probability). If all else fails, just diff the octrees as a starting point (by constructing a new octree which has nodes if and only if the old one and the new one are different at that node) and send that over for the client to reconstruct using his old octree.
The octree lends itself well to your geometry as well, and to your gameplay since you're only removing blocks a few at a time and that change is localized (i.e. you're not deleting random blocks from all over the map) which should make this rather efficient.
If you're already doing that, well, 44kb sounds a little excessive for a single block..
Another option is to not send octrees at all but only changes in blocks (deletion, addition, etc..) and let the client figure it out, which may be easier to implement. But I guess it depends on how your octree and netcode are set up.