Having same issue but on T-Mo HTC One after 4.3 update. Problem is I can't do your unpair fix cause my keyboard isn't showing up in the list of paired devices (even though I've paired it in the past), nor can the scan find anything new... Very annoying, any thoughts?
Posted via Android Central App