"But to not believe someone from the get go, for me says more about me than their integrity."

I would think that their level of trust and past experience is more in question than their personal integrity. Once you have been hurt so many times you come to expect it. I am not necessarily speaking on a conscious level I mean that we have all built up odd reactions and defense mechanisms as a result of our past experiences. To live a happy and productive life I believe that it is vital that we identify and work around these issues.