I moaned to BHX extensively about this on Twitter when I got back from Dubai in November.
It was so bad I am sure I could have flown to LHR and been home quicker, a point I made to them.
They accepted it and said they were speaking to the Border Agency about improving wait times. However, when you see what the BA's wait time target is, BHX is actually "good":
Waiting times at the border
With tougher checks now in place at the border you may have to wait a little longer to get into the UK, especially at peak times. We use scanners to ensure that passports, visas and other official documents are genuine. Our officers are trained to detect forgeries and check that people have the right to enter the UK.
An officer will check your passport and give you permission to stay, if you need it.
We aim to see you within 45 minutes.