"To have been solved" has two interpretations, depending on whether, in the context, the verb "to solve" is regarded as bringing a problem into a state of solution, or the activity of solve a problem. The difference between the two interpretations is that one means that a problem was brought into a state of solution, and persists in that state now. Whereas the other just means that, starting at some time in the past, solving the problem has been habitual.
(In general, perfective verbs and aspects do not only convey completion, but also habitual performance, and repetition!)
Let's use mathematics:
Fermat's Last Theorem has been solved, at last. [A mathematician figured it out, once and for all.]
Quadratic equations have been solved by students for centuries. [Students were given these equations to solve in the past, and continue to do so.]
Since "has been solved" has multiple semantic interpretations, so does the negation "has not been solved".
This obscure puzzle has not been solved by anyone for decades. [Before that, it had been solved by people, but then it fell out of popularity.]
The ignition problem in my car has not been solved. [Isn't in a fixed state.]
The context makes it clear whether we are talking about a permanent state, or habitual solution. In your context "it seems that the problem has not been solved" almost certainly refers to a permanent state: "the problem has been solved" means that the problem transitioned to a solved state, and persists in that state until now. The negation "has not been solved", in the same sense, means that "the problem is not in a solved state now".
Both interpretations do not strictly rule out a past vaccillation between a solved and unsolved state; the construct isn't expressive enough to distinguish such situations. For the kinds of problems which can be solved and then re-appear, "has been solved" doesn't mean that it only took one attempt, and so "has not been solved" also doesn't mean that there hadn't been multiple attempts which ultimately failed.
Let's look your three alternatives:
but it seems they were solved. (pure past)
but it seems they have been solved. (pure perfect)
but they seem to be solved. (present, "they seem" is used)
do anything different, semantically, to fix the perceived problem.
1) opens the possibility that although problems were solved, they may not be in that state now, "but seems they were solved, and then re-appeared and now remain unsolved again."
2) doesn't make a difference. "they seem to have been" and "it seems they have been" are not substantially different. There is just a shift between making "they" the subject, and the anonymous "it". This is possible because in neither sentence is the real agent of problem-solving present: they are both passive sentences.
3) is just an observation on the present state, but the meaning is not substantially different from "have been solved". Though the allusion to the past is missing, of course if problems existed in the past and do not exist now, then they were solved in the past. "have been solved" states that explicitly, "are solved" leaves it implicit.
In this entire discussion, the "have" + "be" construction is red herring, by the way. What "have" + "be" is doing is concealing the agents who solve the problem, and creating passive sentence based on "to be solved" rather than "to solve" which is an unnecessary complication. Whether the sentences are active or passive has no bearing on the semantics; it is only a distraction, because the analysis of the tense and its semantics remains the same over the active versions:
Passive: There were some problems at first, but they seem to have been solved.
Active 1: There were some problems at first, but people seem to have solved them.
Active 2: There were some problems at first, but it seems (that) people have solved them.