Ok, I need to set the scene a bit. I and playing as humans (modified the name to Earth Commonwealth) and I'm doing ok, I'm in a little corner of the galaxy at war with the Drengin. My allies, the Torians, are also at war with the Drengin. On the other side of the Galaxy is a class 19 planet, I want it. Any colony ships the Drengin send are destroyed by the Torians, the Torians show no interest in it so I see my opportunity. I send a colony ship off to colonise the planet, the ship is shot out of the sky by the Drengin, dang. I send a second colony ship under Frigate escort. Unfortunately halfway through Torian (my ally) space I get the "Remove your ships or we will remove them for you" message...from my gorram ALLY! I ignore it as I really want that planet. Just after colonising it the Torians declare war on me, the alliance is broken and they take the planet off me!

Now I won both wars (hehehehe) but shouldn't races start to trust you after a little while?

I'm yet to upgrade to 1.31 so it could be that but if there isn't already one this may be a possible future bug fix.

Edit: I should also point out that the ships escorting the colony ships were outdated flying bathtubs that posed no threat to anything.