Actually, you are correct StoneyVK. Media can be burned at a lower speed than it is rated, but never should be done above the stated speed.
My guess is that the firmware of your drive is simply out-of-date and still doesn't support the media. Check the Toshiba website for a firmware update and see if that solves the problem.
If not, it may also be "bad media" that you acquired. Every once in a while a "bad batch" is produced and you may have received the raw end of it. Try out OTHER 16x media and see if that works. Good luck.