Based on the pasted results I'm pretty sure there's nothing wrong with walk and listdir.  But it sounds like Serhiy will check to make sure, so we'll wait for his report.

The byte string vs the coding cookie is an interesting observation, but is a separate issue and should probably be raised on python-ideas, since I'm guessing it the current behavior was a conscious design choice.