In addition to checking the deadlock trace, have you done anything "interesting" with things like DDL triggers? You can definitely get yourself tangled up in knots if you happen to have a misbehaving DDL trigger that you've forgotten about-- I've done that to myself on my local instance a few times.
Are you saying you looked at the deadlock trace and the trace indicated that the session deadlocked with itself? A deadlock inherently requires at least two different processes holding locks and blocking each other. It shouldn't be possible for a session to deadlock itself (outside of, maybe, some autonomous transaction oddities). Can you post the deadlock trace that leads you to believe that the session deadlocked with itself?
*** ACTION NAME:() 2012-12-13 15:28:25.874
*** MODULE NAME:(SQL*Plus) 2012-12-13 15:28:25.874
*** SERVICE NAME:(oramult) 2012-12-13 15:28:25.874
*** SESSION ID:(1062.879) 2012-12-13 15:28:25.874
DEADLOCK DETECTED ( ORA-00060 )
The following deadlock is not an ORACLE error. It is a
deadlock due to user error in the design of an application
or from issuing incorrect ad-hoc SQL. The following
information may aid in determining the deadlock:
Resource Name process session holds waits process session holds waits
TX-000a002d-0098a33e 22 1062 X 22 1062 S
session 1062: DID 0001-0016-0000000C session 1062: DID 0001-0016-0000000C
Rows waited on:
Session 1062: no row
Information on the OTHER waiting sessions:
End of information on OTHER waiting sessions.
Current SQL statement for this session:
delete from obj$ where obj# = :1
Very odd - the other strange thing is that the trace file shows a delete from obj$ implying that an objects of some sort is being dropped when you try and create something? I can only think that this is a recyclebin issue maybe (try purge dba_recyclebin) or there is some ddl trigger in place doing something, or as you first implied a dictionary corruption of some sort.