This machine was in for service a few months ago for a video problem in which some parts were replaced so it makes me wonder if this problem is connected to that.
Yes, that is the most likely problem. If they didn't use identical parts then the disk wont work. The recovery disk that HP sent you will only work with the particular hardware that that computer shipped with.
You should contact HP and explain your situation.