Just the other day I rang my friend in Kobe and she said 'moshi moshi, moshi moshi' in the most beautiful Japanese I have ever heard...then, when she realised it was me, slipped back into her Kansai dialect...I had never noticed how terrible the Kansai dialect can sound until that day...
I have met many Japanese people who are polite to a point of coldness but I also have three friends who I would not swap for the whole world.
We are very close friends but I think that the case is slightly exceptional because we were in a sports club together (so, since I joined there was that sense of 'uchi' we were doukyuusei and saw each other almost everyday. Even when I got into a flight with another club member, they stood by my side (even though he was handsome, Japanese and they had known him longer) and I have never had such honest and loyal friends my whole life.
However, I think that under these circumstances, we became close friends but under other circumstances we would not have gotton to know each other.
Also, it took a lot of time to become friends. In that time I had to improve my Japanese a LOT and get beyond the normal conversation.
So, even though Japanese people have this cold politeness to them, I still think it is possible to make friends. But also extremly difficult.
I think that probably one of the most important things is to be in the 'uchi'..not necessarily accepted (because I do not think that you will ever me fully accepted) but neverthe less in