Well, a close friend of mine helms a moderately well-known metal band (albums charted in Germany, high on the UK Rock Charts and on the Billboard Heatseeker charts in the US) and after two successful albums, a few large European tours and a month touring the US (in itself a big feat for a European metal band), they are still 'down' by a figure in the order of tens of thousands of GBP to their record label. It's definitely a tough game.
Sounds like bullet.
See, the thing is, if they're only down by tens of thousands of £, which is like dozens of thousands of US$, they would earn out from that in short order if the album revenues were similar to their merchandise revenues Palmer cites here.
Advances run from 10k to millions, depending on how many albums the music executives believe you will sell, and how badly they want to distribute your album.
I know more about the book publishing industry than the music one, but I'd guess that to get million dollar advances you'd have to be a band with a track record, or at least one in a bidding war between labels.