isinstance(x, list) when iterating a list containing strings and lists

I think that your answer is OK here -- Although I might change it to

if not isinstance(x,basestring):
   ...

to make it a little more accepting depending on the expected input. Ultimately, some problems you need isinstance which is why it still exists in the language.

That being said, the thing about this problem that is un-pythonic is the data-structure. In python, if a problem seems really hard, it probably means you're storing the data in the wrong way ... (Of course, I realize that you had no control over what the original poster of the other question's data structure was ;-).

Basically, I guess that my view is that isinstance is the hack that you need to make lemonade when your colleagues/some library writer somewhere gives you lemons -- Otherwise you avoid it where possible.