You don't say what speed(s) you've tried burning the discs at?
Assuming these HP discs are indeed made by CMC as Evilboy suggests, then have you tried burning at 8x?
If the DVD-R are CMC MAG. AM3, then burning at 8x might do the trick. I tend to burn all my own CMC MAG. AM3 at this speed, especially for movie backups. As for CMC MAG M01, well...I tend to stay away from those LOL.
Agree with Evilboy re: the Verbies, but if you can use these HP/CMC discs and not let them go to waste then it might be worth giving 8x a shot.
However if it's just that particular DVD-R make/brand your player doesn't like, maybe use the discs for data storage instead.