I see your point, but I'm not sure Chomsky was espousing anything magical (as in pseudo-science) by saying the Fibonacci sequence is found in nature and isn't well understood why. Present company excepted, perhaps.
I also try to keep in mind that the term "magical" is often rather amorphously applied.
Some call pseudo-science "magical" due to ignorance.
Some call some science "magical" due to ignorance.
However, some call certain science "magical" not due to ignorance, but as a respectful nod towards the vast complexities involved that we still don't know (and perhaps never will) that surround the complex "nature"[0] of science.
If you haven't already read it, I think this is a pretty interesting take on it (in a sense):
http://www.amazon.com/New-Kind-Science-Stephen-Wolfram/dp/15...
Series of followups 10 years later:
http://blog.stephenwolfram.com/2012/05/its-been-10-years-wha...
[0] https://www.youtube.com/watch?v=Bo3R3LBjDek (Love And Rockets - "No New Tale To Tell")
http://www.amazon.com/New-Kind-Science-Stephen-Wolfram/dp/15...
http://www.amazon.com/dp/1579550088/?tag=googhydr-20&hvadid=...