There are a few key things to understand here.
First, this message does not appear to be coming from Ubuntu. It may be in HP's BIOS. Maybe the reason it doesn't appear when you boot windows is due to Windows' fast boot feature or something.
Secondly, when Windows is reporting that the battery is fully charged it is reporting on something different. This is the difference between battery charge and battery usable capacity. A battery can be 100% charged, but deterioration since manufacturer could mean that at 100% charge it's only around 60% as much as when the battery was new. That's the difference between charge level and usable capacity level.
So, this message is indicating that the usable capacity of the battery has dropped, to such a degree that it's indicative of poor performance of the battery and possible continuing deterioration, so it should be replaced to return to best operation.
However, you also said that the battery was replaced with an aftermarket (ie, non-HP) battery.
This means that all bets are off in regard to the usable capacity rating, and you can't trust that what it's telling you is accurate or is just a result of the aftermarket battery not confirming to the same way of reporting things as an official battery. So there is not necessarily cause for concern.
The non-official battery may have a poorer capacity than the original (and may not even live up to its own claimed capacity) but this doesn't mean it's due to damage or degradation, and either way, your laptop has no way of measuring this properly as it can only trust what it knows about the battery, and the battery is pretending to be something it isn't.
Some aftermarket batteries do a better job than others about reporting information to the host computer, but you don't have assurance.
As long as the battery is working to satisfy you, there's not necessarily any problem at all. Though, if this error message is coming repeatedly and that's annoying you, then you probably should contact whoever sold you that battery as you ought to expect that even if a battery is not fully compatible or doesn't report its usable capacity correctly, it should at minimum not result in consistent error messages every boot!