If you are mapping the gift attribute category to an incoming value and that value has a leading or trailing space then you will get this error message even if the category appears to exist in RE. (If it appears in RE with the leading or trailing space then you will not get this error message)
This has been fixed in version 2.9 of Importacular.