ArcMap and ArcCatalog seem to cling to locks on FCs (especially in PGDB and sometimes even FGDB). So if you had run your model, and had the result FC added to ArcMap, and then rerun your model (using the same output fc path) I bet that it is having trouble deleting it, since it had been added to the active session of ArcMap at one point. Try exiting ArcMap completely, restart it, and then rerun the Model. Does it work then?