I know of at least one person who was hired for a postdoc and began work before his dissertation was officially filed. I also know of someone who applied for and was interviewed for a tenure-track job; she didn't get the job, but if she had, she would have begun work before receiving her PhD (and the people offering the job were aware of this).
However, these were both cases in which the people were clearly on track to complete their PhD and simply needed more time to see it through (e.g., more rounds of revisions). In other words, they were not people who hadn't finished their thesis, but people who hadn't finished their thesis yet --- the people hiring them were confident that they were obviously going to finish. Indeed, they basically were finished with the actual writing, but were just making some revisions in response to committee comments.
You don't say exactly why you haven't finished, but the phrase "advisor problems" suggests it is not just a matter of needing more time to do another round of revisions. No one will accept you if the reason you haven't completed your thesis because you are locked in some sort of stalemate with your advisor. However, they may accept you if you are clearly on track to finish, even if you may not actually officially receive the degree by the official deadline. I would imagine that in most cases the letter of recommendation from your advisor would be a major factor here. If you haven't received the degree yet, but your advisor says your research is coming along nicely and the end is in sight, hirers may be satisfied. If your advisor mentions that the two of you are at an impasse over substantive issues (i.e., he wants you to do something with the thesis that you haven't agreed to do) that will raise a red flag.
As a side note, my impression is that many hirers would not see a problem if you have not officially received the degree yet due to purely procedural problems (e.g., it has been approved by your committee but not yet officially filed because your margins were the wrong size). I gather that is not the nature of your situation though.