Do you mean different forests? Different domains within the same forest shouldn't have problems.
You don't say what operation you are trying to perform. As you have opened up queue permissions then it won't be a send(). I expect therefore that you are trying to read from the queue which uses the RPC protocol and has a different bunch of security obstacles.
Best Answer
I don't think you can, but you can always deleted and create a new private queue by the name you desire can you not?