Two ways you can do this depending on what software you have.
With DVD Studio Pro 1.5 and Final Cut Pro, I would use FCP to composite 4 videos in a single canvas, something like a PnP feature, but 4 videos. I would create a background in Photoshop and import that in as a v1. Just adjust the size of each video on v2, v3, v4 and v5. I would make them 15 or 30 seconds long, export to .m2v with no audio.
With the new DVD Studio Pro 2, I would simply batch export 4 videos, each 15 or 30 seconds long and draw a button the size I want in the single layer object and drag-n-drop each of the 4 videos onto those buttons. They will each become buttons with the video inside. You can add an PCT background and even text to each of the buttons right inside of DVDSP2.
In both cases, a PSD layered menu will not work, unless 2.0 has some new feature I don't understand as of yet.
In 1.5, the extreme sports tutorial uses this technique. Take a look at the source media. It is really a composite, brought in as an m2v.
In the new DVDSP2, as a test, create a still menu, draw a square and drop a video in it. In the properly inspector of the button asset, you will see you can add text. Adjust the color states and simulate it. You will see how this works and can go from there.