使用台数が制限以内なのにエラー表示になります。

メールですぐに問い合わせてもいいかもしれません。
自分の場合だと、すぐに認証されました。
ファミリー3年で5台使用。PCが2台、3台がNexus9、Nexus7（2013）、Nexus7（2012）。
PC用3年版1台。
PC3年版1台が期限終了で、Nexus7（2012）からアンインストールして、期限が切れるPCですぐにファミリー認証できました。
それから、WinPC1台とタブレット1台が増えたので、またファミリーを購入。
PC4台をすべて新規ファミリー。前のファミリーをタブレット4台に割り当てました。
PC3台分ファミリーをすべて新ファミリーに更新し、4台目のタブレットで旧ファミリーで即認証されたので。

インストールする時にはアクティペーション情報がメーカーサイトに捕捉されますが、反対にアンインストールしてもメーカーサイトでは関知できません。５台登録済みなら５台のままです。
パソコンが動作不能(故障)に陥っても同様です。

ソフトによってはユーザーがホームページにアクセスして該当のパソコン登録を削除する事も出来ますが(ウイルスバスターがそうです)、そのようなシステムない場合はメーカーサポートへ電話で相談するしかないでしょうね。