Make a black/white mask (black bars top/bottom, white in center) at the correct resolution/size/pixel aspect ratio, in Photoshop (or whatever software you like) and key it over your 4:3 footage.
You don't need to create anything. You can just toss a Crop filter on your whole comp. 4:3 -> 16:9 you need to crop about 60 pixels each top and bottom.
EShy - Premiere's default letterboxing title is wider than 16:9 - don't remember how much, but it's wider (stupid that they don't have presets for all of the standard aspects but....)
i'll nest a project in a 2nd one and add a horz barndoor wipe to the whole film. Adjust the start and end points so that they're exactly the same (roughly 40% i think or maybe the opposite 60%)...one caveat, P will output the black tops and bottoms so the video will still be technically 4:3 ratio...sometimes that sux cuz if you have artifacts, your black bars will have them too. also issues with wide screen tv's but not sure about that too much cuz i don't have widescreen tv..