This is indeed the issue. Using provable bounds loses too many bits for complex FFTs to make sense for long multiplies.