Mine came out of the box @ 75 percent. A couple hours later I thought it would be a good idea to unpair my phone from it. When I tried to re-pair it, it said the battery was too low and I couldn't get past the Language setup screen. Once I "plugged" it in, it was able to get past that screen immediately.
Which means it has to be at least 50% or more battery to pair successfully.