In case anyone cares I solved this myself. I think it's just a bug in excel.

The first nominal value I was using of -0.0001 to start the CF's with a negative value I changed to -5. Luckily my CF's are 100k or larger so the IRR will not be affected. This small change in combination with the SIGN guess logic described above fixed the problem....

I guess sometimes guess and check is the best way when you are dealing with an excel bug workaround.