That statement is there because having an Advance Parole doesn't negate any of the reasons why someone might be inadmissible (ie. criminal record, overstay before approval, etc.). If there is no real circumstances which might lead to someone being denied entry due to existing problems, then they should be safe with an AP.
The ultimate authority to allow anyone to re-enter the US is in the hands of the border authorities. Even having a visa does not guarantee admissions or re-admissions. The only guarantee that ensures someone is allowed to enter the States is if they are a US citizen.
So, while that statement is there warning you that denial of admission is always a possibility, I haven't heard of anyone having a problem with being denied while trying to re-enter on an AP. You just need to be aware that the possibility exists but is probably only a serious consideration if you have another factor affecting your status in the country. I do know that there are all sorts of warnings that say don't even bother to apply for an AP if you have an overstay of any significance as you will be denied entry, things like that.
Technically, while it seems a moot point, a person returning on an AP isn't actually 're-admitted' to the US, rather they are 'paroled' into the US. The difference, while it seems to be just a definition, actually has legal implications that shouldn't have an impact on your situation, but can under specific circumstances.
Ok, probably just made the waters even muddier for you . . .