Why is windows needed? Just use aticonfig.

There's no need to flash anything for most cards out there.

Thanks for the guide!  I actually did this myself a couple weeks ago and it's working great.  Just a suggestion for people considering this: BACK UP YOUR BIOS!  I made this mistake and realized after I reformatted back to Linux that my 5970 didn't flash correctly, so I had to go through a bunch of hoops to fix it.  As long as you backup your BIOS, you can easily create a USB boot disk and put the previous BIOS back on using ATIFlash. 

I'd recommend creating a DOS USB boot disk while in Windows and throwing ATIFlash and your backed up BIOS's along with any new BIOS you want to try so you don't have to waste a whole day of mining. 

Here's a link to a quick guide on creating a DOS USB boot disk in windows:
http://www.bay-wolf.com/usbmemstick.htm

Many card manufacturers have different hard limits set in the BIOS of the card.  This can even vary between individual cards from the same manufacturer.

Out of 5 GigaByte 5870s, I've found 3 different clock limit settings on them:
Memory: 300-1200, 300-1400, 600-1200
Core: 300-900, 300-950, 300-1200

HIS and MSI Lightning's also have their own limits (although my 2 MSI Lightning's allowed obscene overclocking to the point the thing would melt if it didn't crash first).

Flashing the BIOS will remove these imposed limits.  aticonfig will not let you go around them.

I downloaded a popular BIOS file from an Asus 5870 which I then flashed to any cards (using atiflash) that didn't allow me to use the clocks I wanted.  A little google searching will lead you to the Asus.rom (BIOS) file and a guide on how to use atiflash.

Are you using AMDOverdriveCtrl in Ubuntu ?
Which version of AMD Drivers ?