Since you say the issue is his problem solving skills, not knowledge of the language or your shop's rules and practices, I really don't see what the question is here. Certainly you should give him feedback on his performance - not to do so would be an injustice to him: By doing so you give him a chance to improve. If you don't do so, he may think everything is fine and never try to improve, making things only worse, such that you may have no choice but to terminate him.
As an employee I always appreciate constructive feedback from management, especially if I'm new to a job. Just make sure to present your criticism in a delicate and respectful manner, particularly if you believe he has the potential to overcome his shortcomings and become a valuable employee - you don't want to lose someone who may be talented because you came down too hard on him.
In addition, once you have given him your feedback, you will have done your duty as a manager by putting him on notice, so if subsequently he does not develop the way you hoped, terminating him will not be a great shock to him.
As an aside, this incident should be a lesson to you when hiring a developer: Problem solving skills are probably the single most important thing a developer needs, and they come from talent and experience - not really something you can learn in school or from a book very well. Not so for most of the other skills required to be a good developer. IMO problem solving skills within a programming and IT context should be the main focus of such an interview - the rest can be learned on the job if you are sure that the fundamentals are there - that the candidate is indeed a competent programmer in the general sense, with respect to the position you need to fill.
Having said that, his future with you may not all that bright, because problem solving skills are indeed difficult to acquire, if the innate talent just isn't there.