Your example is a textbook case of a dangling modifier. The problem is that the subordinate clause of your sentence ("Having recently been completely remodeled") modifies the subject of the independent clause ("they thought the house lacked charm").
In other words, the sentence says that they have been completely remodeled, while the intent of the speaker was likely that the house was completely remodeled. Hence the error.
The most obvious way to fix the sentence is to rewrite it so that the house is the subject of the independent clause:
Having recently been completely remodeled, the house lacked charm to them.
or make both clauses independent:
Because the house has recently been completely remodeled, they thought it lacked charm.