The earlier problem had to do with the character '&' in item names, descriptions, etc.; even though we were properly encoding per their specs, it was still causing their system to choke, so as a workaround we ended up just replacing '&' with '+' for PPA submissions.
That was kind of a special case, since that character is significant in the format that values are passed to the PayFlow Gateway. The format looks like a fairly standard name-value pair, i.e. "name1=value1&name2=value2&name3=value3", except instead of the standard %-encoding for values they use a proprietary length tag format (so "vim&vigor" becomes "vim&vigor" rather than the web-standard "vim%26vigor").
The point of that technical trivia being that I wouldn't suspect this to be the same problem; that was a very specific case related to a reserved character. Then again, I wouldn't put it past them to be choking on some other non-alphanumeric character; from what I've experienced the PayFlow Gateway is a typically antiquated payment card system, still stuck in the ASCII era.
Are there specific items you're seeing this problem with, or does it seem to happen regardless of what items the buyer has put in their cart? Any additional info you can provide may help us narrow it down.