I think YNAB is most useful for people who would make better spending decisions by knowing what their money is allocated towards. My parents used to do the paper budget and stopped after money stopped being tight. If you're already very frugal *and* you're banking two out of three paychecks, why waste your time? If you're not sure whether you've saved anything in the last couple of months, budgeting and tracking is immensely helpful.
I used Quicken for a long time many years ago until I got married. I started because I bounced a check back in my college days thinking that I had the money in my account to cover it, but turns out that I'd written one too many checks, and my boss didn't pay me on time. When I got married, my husband thought it was a waste of time so I agreed to stop and see how I felt about it. Never went back to doing either budgeting or tracking spending until last Christmas, when I bought YNAB. I fell off the horse pretty quickly and am getting back on now (using the fresh start).
I haven't tried Mint, but YNAB is huge for us because we have both irregular spending and irregular income. The idea of filling up a bucket rather than putting numbers on a spreadsheet and seeing if they match at the end of the year, is absolutely key for us. Doesn't do any good to have a huge outlay in August that has no income until December. Quicken budgets were a poorly done "feature" that never worked for me.
Since we do have various savings goals (house, car, Christmas vacation, private school, furniture), I do like knowing where the money is allocated, and I would make decisions based on it. I think the biggest tradeoff for us might be that buying a house might require homeschooling, so I'd rather have that fact staring me in the face in May when I have to sign the contract, not when I have to make a payment--if I don't have enough in the house downpayment bucket, where is that money coming from then? What are the consequences? If I haven't saved up enough in the school bucket, then realistically, should I be signing the contract?
I'm also hoping it'll help me be more conscious of where the money is being spent and that we'll get in the habit of looking at our choices at the end of the year. I do most of our purchasing on Credit card, so I do have end-of-year tallies, but it doesn't always categorize it right, and certain things may be Gift-in-Kind that end up in other budgets categories.
I've had a good experience with the iPhone link to my desktop via Dropbox, btw. I"m hoping to get into the habit of entering everything when I'm checking out, or at least before I drive away.