Check View | Toad Options | Oracle | General. There is the option to direct Toad to use a specific explain plan table. Verify that the correct explain plan table and schema are specified. Verify that the current connection/schema has privileges to that table.
If none is specified and no user defined explain plan table is expected, verify that there has not been any changes to the schema privileges and its ability to create tables and/or access the plan tables.
