I had a similar decision to go through, and I'm in a PhD program in machine learning now myself! PhD's might not be the trendiest thing in the startup world, but they're not a detriment at all from what I've heard and seen. Interned at a well-funded startup with 40 employees at the time, and we interns were literally the only tech people there without advanced degrees; many were ex-Googlers and the like. Similarly, at Microsoft I heard from many that as long as you can demonstrate that you haven't lost your touch for coding (do implementation + theory!), you're at no disadvantage relative to where you were before the PhD, and quite possibly at an advantage if you want to do more research-oriented things. Me, I may end up catching the academia bug while I'm here, but I'm not worried about losing my "in" in industry.
I'm almost done with my PhD, and for people that don't want to stay at academia, I find extremely important what btown says about not doing only theory.
Very rarely you will find a job where you'll only have to do theory, and even if you think you still remember everything you learned in your Bsc, you probably don't. Also, some of the things you might still remember, may not be of any use in the job market anymore.
From my experince, I recently started being contacted and going to job interviews at major companies and I had to spend some time going through some course material and MOOCs, even if I been doing some code during my PhD.
Regarding the PhD experience, choose your advisor and group very carefully. You'll spend a lot of time with them. Also, during almost 2 years I was working with a really bad crazy advisor, that was pushing me to the limit for his interest. I was almost quitting but decided to change advisor and I'm really enjoying this now.
...now back to that problem set...