I would RMA the machine if under one year warranty, or return it to the store if possible for full refund.
It must be really new if there is such a BIOS lock as the previous ones were easy to get around and never this much of a PITA. HP needs to own this, as it will be deal-killer for new purchases if they don't.
Let their Customer Service (not tech support) know that it's being aired here and we want to know what they plan to do about this besides charge for a new mobo, which is unacceptable and a rip off of the consumer.