I have the same issue with my brand new Samsung BD-C5500C. I bought it at Costco this afternoon.
Once I plugged in the HDMI cable and turned the player on, it automatically turned my TV on. I didn't think it could do that. The display on the front of the player says "SETUP" in English but the information displayed on the TV is all in Korean. It has a funky wood-grain kind of background with one button in the middle outlined in blue. (I did not know it at the time but the characters in the button mean "Korean." Note that there are no other buttons with other languages at this point.) There is no option to select the language as indicated in the quick start guide.
After doing the usual reset/power-cycle nonsense with no effect, I started playing around with the menus. I had planned to return it to Costco so there was no harm in it, right? Lo and behold, I figured out how to fix it. Step by step, this is what I did; I hope this helps somebody:
From the "wood-grain" screen: In the middle of the screen is a button outlined in blue with some funky Korean characters on it. At the top, a "gear" and some more Korean. At the lower right corner, the "select" icon, "return" icon and some more Korean.
Press the select icon and it will take you to the aspect ratio selection. Select the first 16:9 option (you can change it later, right?) On the next screen there are 3 buttons outlined in blue (the third one says "PBC(WPS)" Don't select any of these. Instead, press the blue "D" button on the remote two times. It takes you to the player's home screen. All options are still in Korean at this time. Use the arrows to navigate to the "gears" and select it. On the next menu, use the down arrow to go to the 5th option which consists of two characters with little circles that look sort of like a zero and a one connected by a line. Press the right arrow to go to the expanded menu. The first option is the language option tho you don't know it because it's still in Korean! Press the right arrow again and the language menu will open. Select the lingo of your choice and voila! Now, continue with your setup.
Out of the box and hooked up it is stuck in the setup mode with all Japenese Language and I cannot get it to English using the remote