Korean hot paste---kochujang.

In NYC, it's often best to branch out to the boroughs for ethnic shopping/restaurants. For instance, there's a big Korean population in Flushing, Queens - hence, lots of shops/restaurants. (There are no doubt enclaves in other boroughs, but that's the one friends in Astoria - Greek food heaven - have mentioned.) I believe there's a large market there called Han Yang? Hang Yan? Hanyang? You get the idea. Anyway, it's all just a subway ride away.

fyi, I have a tub of the chile paste in my refregerator which was purchased from H Mart by a Korean woman I tutor. Her mom showed me how to make bibimbop. It is Korean writing on the front label except the brand Pulmuone. English language on back just says Korean Hot Pepper Paste, imported from Korea by Pulmuone Wildwood, Fullerton CA Ingredients: Red Pepper, Wheat flour, Soybean, Salt, Molasses.
http://maps.google.com/maps/place?rlz=1T4GGLL_enUS361US361&um=1&ie=UTF-8&q=diamond+bar+h+mart&fb=1&gl=us&hq=h+mart&hnear=Diamond+Bar,+CA&cid=8116464277877442480

First of all, thanks for all the thoughtful replies. I'm quite familiar with Kalustyan's because I used to stay in hotel on 28th, about a block away. But I've always thought of it as a resource for ingredients from India and the 'stans rather than Korea. Checked out HMarts website but their store locator is useless. Found Maangchi on my own, but again a confusing website.
I'm an old hand at Korean barbecue but now I'm on a quest to make some really good bipimbap. I have a source for big fat goose eggs; funny how one ingredient will set you on a path to another.
Recently I moved out of a So Cal town where the convenience stores and dry cleaners were all run by Koreans. Some of whom became really good friends. But they didn't stock much in the way of authentic Korean stuff. It was a beach town and mostly they sold beer and cigarettes and sports drink to the tourists.
I'm looking forward to reading "My Korean Deli" by Ben Ryder Howe.

You shouldnt have any trouble finding it in NYC or LA (any korean store should carry it). I live in a small urban town in Virginia, and have 2 korean stores within a couple miles of each other, and they have a few options for gochujang. Be careful when you buy it though, it comes in different heat levels, right now I have the "So Hot" level in my fridge, and its a little TOO hot. If youre looking for a great bulgogi recipe, let me know...and if you like hot foods, be prepared to become addicted to gochujang, I know I am.

Today's NYT food section has a small item about a new store, Shi Eurasia, at 143A Orchard Street (near Rivington). Bet you can get the paste at any number of stores in NY (or LA) but this shop looks kind of fun, and, it's a great eating neighborhood as well. I'm guessing you've been to Kalustyan's but I hadn't been until last month. If I didn't have a car waiting for me outside with grumpy family members, I'd have been in there for hours. So much from so many different areas in one little store!

I've been dismayed at what the huge Burlington, MA HMart does not carry vs. the small Chinese/Asian grocer on Camb. St. in Burlington that has everything Asian.

I agree, HMart is a great Korean grocery chain with several locations in/near NYC and So.Cal http://www.hmart.com/company_new/shop_main.asp
It also appears from their website that you can order from anywhere in the continental US and they have plenty of red pepper paste.
http://www.hmart.com/shopnow/shopnow_newsub_mid.asp

Another resource for looking for Korean ingredients in a foreign city is Maangchi's website. There are user-submitted summaries of Korean groceries around the world. It isn't terribly complete, but it is useful. I'm not familiar with LA, and I haven't lived in New York for 8 years, but the places listed in the city Han Ah Reum (most extensive selection, in Koreatown), Sunrise Mart (Japanese), and M2M (very convenient to my apartment, but more of a takeout snack store than full-on Korean grocery, though it did have any essentials I happened to be looking for) had gochujang when I lived there. I would often stop at the Hmart in Fort Lee when visiting my relatives, just across the George Washington bridge and revel in it's variety and spacious floorplan.
http://www.maangchi.com/shopping/us

HMart is a chain. We have one now in Mass and I LOVE it. Not sure if they do mail order. www.hmart.com

My NYC sources say: "Kalustyans on Lexington Avenue between 28th and 29th streets. They carry everything you could possibly imagine ... of course, at slightly higher prices for some of the stuff."

LA's Korea Town begins just east of Vermont Ave and is roughly bounded by Beverly Blvd to the north and 6th Street to the south. Largest Korean population outside of Seoul. I'm just hoping someone can spare me the footwork.

I put the word out to my NYC chef friends.

Now I'm curious, too. I'm going to LA in May.

There is a fantastic large Korean grocer in Diamond Bar (LA County) called H Mart, they will have everything Korean. And other Asian regional items too.