PhD hopping due to professional but non-research issues

Is this a valid reason to give other departments when inquiring about working with them?

Yes, absolutely! By not providing the necessary resources for you to begin on your expected start date, the university has released you from any obligation to attend. You are a free agent.

How can I formulate this in a way which is positive?

It's not clear that you need to formulate it at all. Since you never attended your intended university, you are under no obligation to mention it in your CV or application. At most, you may need to explain the one-year gap in your education/employment record, in which case — if asked — I'd suggest something simple like "I was admitted to the graduate program at [University X], but I was unable to attend because of unforeseen delays in processing immigration documents, which was out of my control."

As a courtesy, you should also explain your decision to pursue other opportunities to the department that admitted you, and in particular to your prospective advisor (if you have one). In fact, I would recommend starting there; your department/advisor may be able to pressure the university bureaucrats into providing the paperwork you need.