What version ArcDesktop are you using? What version is the geodatabase (If you are using ArcDesktop 10.1 or higher you can get this info by right clicking the .sde connection in ArcCatalog-> Properties-> General tab, there is an upgrade status section that tells you the version of gdb)
If possible to test, are you able to use single use licenses without issue (i.e. could this be due to License Manager handing out concurrent use licenses?)
-TM