I’ve recently been uploading lots of my SD 4:3 movies to Youtube. Now that youtube is 16:9 there’s empty space on my videos with pillar boxes. I’d like to fill that space in with graphics kinda like how ESPN does when they display 4:3 footage on the HD channel (It’s the ESPN logo on the sides). How would I go about doing that? Theoretically, I’d presume that I could start with a 16:9 project, add the pillar box graphics to the side, import my 4:3 video and picture in picture it in the center. Or am I missing some obvious solution? I have access to Avid, FCP, and AE for editing programs.

Yup, that's the way to do it.