Separate construction phase from constructed phase I am sure you can find many weak spots, please let me know about them.
My main question is if this is a sensible approach to separate the construction phase from the constructed phase. 

Basically I have a set of objects that needs to be transformed into similar (but different) objects. Once transformed I want to be able to query these later.

So I have a PartitionedContainersBuilder which deals with the transformation part and I have a PartitionedContainer which represents the transformed query-able.

What I do like with this is that there is no invalid state anywhere and little risk of doing mistakes with member variables. Had Java been able to return two values then I would probably have solved it differently. However with that said, I know for example that calling it builder and build may not be the best thing (it is not the builder pattern).

I would prefer having the constructor in PartitionedContainer do the work rather than a static build - would that be better? My gut feeling says yes, but is there a tangible advantage? 

public class PartitionedContainers {

static class PartitionedContainersBuilder
{
    private LogicalExcelAreaInterface buildLogicalExcelArea(ContainerNodeInterface pContainer, PapyrusInterface pPapyrus)
    {
        // TODO: introduce LeafItemContainer to remove if cases
        if (pContainer.getItem() != null) 
        {
            return pContainer.getItem().getLogicalExcelArea(pPapyrus);
        } else {
            return new MutableLogicalExcelArea(1, 1)
                        .withCellWidth(0, 0, pPapyrus.getWidth())
                        .withCellHeight(0, 0, pPapyrus.getHeight());
        }
    }

    public PartitionedContainers build(final ContainerNodeInterface pRootContainer, final Map&lt;ContainerInterface, PapyrusInterface&gt; pPapyrusFromContainer)
    {
        final Map&lt;PartitionedContainerInterface, PapyrusInterface&gt; lPapyrusFromContainer = new HashMap&lt;PartitionedContainerInterface, PapyrusInterface&gt;();
        final Map&lt;ContainerNodeInterface, MutablePartitionedContainer&gt; lPartitionedContainerFromContainer = new HashMap&lt;ContainerNodeInterface, MutablePartitionedContainer&gt;();

        for (final ContainerNodeInterface lNode : new NodeCollections&lt;ContainerNodeInterface&gt;().getAllSortedTopDown(pRootContainer))
        {
            lPartitionedContainerFromContainer.put(
                    lNode, 
                    new MutablePartitionedContainer(lNode.getElement(), buildLogicalExcelArea(lNode, pPapyrusFromContainer.get(lNode)))
            );
            if (!lNode.isRoot()) {
                lPartitionedContainerFromContainer.get(lNode).withParent(lPartitionedContainerFromContainer.get(lNode.getParent()));
                lPartitionedContainerFromContainer.get(lNode.getParent()).withAdditionalChild(lPartitionedContainerFromContainer.get(lNode));
            }   
            lPapyrusFromContainer.put(lPartitionedContainerFromContainer.get(lNode), pPapyrusFromContainer.get(lNode));
        }
        return new PartitionedContainers(lPartitionedContainerFromContainer.get(pRootContainer), lPapyrusFromContainer);
    }

}

PartitionedContainerInterface mRootContainer;
Map&lt;PartitionedContainerInterface, PapyrusInterface&gt; mPapyrusFromContainer;

private PartitionedContainers(PartitionedContainerInterface pRootContainer, Map&lt;PartitionedContainerInterface, PapyrusInterface&gt; pPapyrusFromContainer)
{
    mRootContainer = pRootContainer;
    mPapyrusFromContainer = pPapyrusFromContainer;
}

public PartitionedContainerInterface getRoot()
{
    return mRootContainer;
}

public static PartitionedContainers build(ContainerNodeInterface pRootContainer, final Map&lt;ContainerInterface, PapyrusInterface&gt; pPapyrusFromContainer)
{
    return new PartitionedContainersBuilder().build(pRootContainer, pPapyrusFromContainer);
}

public PapyrusInterface getPapyrusFromContainer(PartitionedContainerInterface pContainer)
{
    return mPapyrusFromContainer.get(pContainer);
}
}
First of all, you are right, what you have there is not a builder class, but more like a factory class. Which is roughly equivalent to a static factory method.

Now, the question of using constructors vs static factory methods is one over which there has been a lot of talk, and for the most part no conclusive, universally-applicable answers. (Just search for "c# constructor vs static factory method" and you will see.) However, specifically for your case, where both the constructed class and the code constructing it are private within another class, the advantages of "discoverability" and "recognizability" that the new keyword has are not applicable, so I'd definitely go with a factory method or class.

With regards to whether you should be using a factory class or a static factory method, I think that the factory class is fine. The overhead for the generation of an additional object which gets immediately discarded is negligible, (especially compared to the amount of work that the object will do,) and might even be optimized away by the compiler. On the other hand, having a factory class instead of a static factory method could turn out to be useful if in the future you decide to introduce some state into your builder.