I am having major inter-personal issues with my manager (A), and approached the leader/manager of another team (B) in the same department to see if he plans to expand his team. Well, B told A about my inquiry, and my manager (A) told me that what I did constitutes insubordination. Is it common HR policy that "feeling out" another manager for a job is insubordination? (Didn't find anything in the Employee Guidebook.)
In general no, talking with another manager about a potential move inside of the company would not be insubordination. However, if in the process of discussing the situation with the other manager you trash talk your current manager, their decisions, or actions that could definitely constitute insubordination. Also if you have been placed on some probationary status then having that discussion with another manager could violate some provisions of that status which might also count as insubordination.
Insubordination is a bit extreme. From you manager's perspective if you wanted to move to another team you should have come to him with that.
When you go directly to manager B it looks bad for manager A as here is a team member that wants to jump ship.
Most likely manager A is going to need to approve releasing you so if you want to go to another team then just go directly to manager A.
Now if you want to discretely find out if team B is expanding then ask a team member you have a relationship with. Now the information is not as reliable but it is not likely that team member will contact your manager. Ask in a way that does not sound like you want to move. When you go directly to the manager it is pretty obvious you want to move.
I am having major inter-personal issues with my manger (A)
And you thought he/she would not find out you were talking to another manager? You proactively escalated the already major issues and your manager would definitely not be happy about that.
In answer to your question, yes, it could be interpreted loosely as insubordination if it is in line with the other previous issues mentioned. If for instance the manager thinks you undermine their authority or something similar regularly. On it's own no, but it's not an isolated incident. You knew (hopefully) that it would get back to them.