Well for each of the six sides, in a vanilla cubemap the corresponding mips are loaded next to each side. When you then save it and create mipmaps it puts all 6 sides together, and the next mip level for all 6 sides together out to the right, and so on. Hard to explain without images, but I don't feel like taking images. I'll do it textually. ABCDEF are all 6 sides, and 123456 are the mip levels. So, left to right you have A1A2A3A4A5A6 then B1B2B3B4B5B6 and so on. When you save it back out again the format is A1B1C1D1E1F1 then A2B2C2D2E2F2 and so on.
What you need to do is select the "Cube Map" option before saving it back out. If you use the Nvidia plugin for Photoshop, it's the 2nd dropdown. The default says "2D Texture" and you select Cube Map instead from that dropdown list. If you use some other exporter, I am not sure if it has the Cube Map option.