So, for the first revision of the board:
FX-8350 4000MHz 1MBx8 8MB Vishera 32nm C0 125W 5200 since F3 BIOS version
http://www.gigabyte.com/products/product-page.aspx?pid=4642#
then
F3 - first release: http://www.gigabyte.com/products/product-page.aspx?pid=4642#bios
Conclusion: The 8350 is supported by the very first BIOS version.
No problem. It's actually the manufacturer confusing people.
"To enable AM3+ AMD FX-Series CPU support, please update your motherboard with the most current BIOS found in your motherboard’s download section."
This warning is confusing.