Please try 5.5 snapshots, this bug should be gone.

I tested and reproduced the issue with PHP55-201306280830

Same on Zend Server CE on Windows with PHP Version 5.5.7 (GD Version: bundled (2.1.0 compatible)).

I used this as test script:
<?php
$interpolations = array(
'IMG_BELL' => IMG_BELL,
'IMG_BESSEL' => IMG_BESSEL,
'IMG_BICUBIC' => IMG_BICUBIC,
'IMG_BICUBIC_FIXED' => IMG_BICUBIC_FIXED,
'IMG_BILINEAR_FIXED' => IMG_BILINEAR_FIXED,
'IMG_BLACKMAN' => IMG_BLACKMAN,
'IMG_BOX' => IMG_BOX,
'IMG_BSPLINE' => IMG_BSPLINE,
'IMG_CATMULLROM' => IMG_CATMULLROM,
'IMG_GAUSSIAN' => IMG_GAUSSIAN,
'IMG_GENERALIZED_CUBIC' => IMG_GENERALIZED_CUBIC,
'IMG_HERMITE' => IMG_HERMITE,
'IMG_HAMMING' => IMG_HAMMING,
'IMG_HANNING' => IMG_HANNING,
'IMG_MITCHELL' => IMG_MITCHELL,
'IMG_POWER' => IMG_POWER,
'IMG_QUADRATIC' => IMG_QUADRATIC,
'IMG_SINC' => IMG_SINC,
'IMG_NEAREST_NEIGHBOUR' => IMG_NEAREST_NEIGHBOUR,
'IMG_WEIGHTED4' => IMG_WEIGHTED4,
'IMG_TRIANGLE' => IMG_TRIANGLE,
);

$img = imagecreatefrompng('image-test.png');
$results = array();

foreach($interpolations as $name => $interpolation) {
  imagesetinterpolation($img, $interpolation);
  $t = imagecolorallocatealpha($img, 0, 0, 0, 127);
  $imgr = imagerotate($img, -5, $t);
  $results[$name] = array('x' => imagesx($imgr), 'y' => imagesy($imgr));
  imagedestroy($imgr);
}

print_r($results);
imagedestroy($img);
?>

Results:
Array
(
    [IMG_BELL] => Array
        (
            [x] => 40
            [y] => 22
        )

    [IMG_BESSEL] => Array
        (
            [x] => 40
            [y] => 22
        )

    [IMG_BICUBIC] => Array
        (
            [x] => 40
            [y] => 22
        )

    [IMG_BICUBIC_FIXED] => Array
        (
            [x] => 41
            [y] => 23
        )

    [IMG_BILINEAR_FIXED] => Array
        (
            [x] => 41
            [y] => 23
        )

    [IMG_BLACKMAN] => Array
        (
            [x] => 40
            [y] => 22
        )

    [IMG_BOX] => Array
        (
            [x] => 40
            [y] => 22
        )

    [IMG_BSPLINE] => Array
        (
            [x] => 40
            [y] => 22
        )

    [IMG_CATMULLROM] => Array
        (
            [x] => 40
            [y] => 22
        )

    [IMG_GAUSSIAN] => Array
        (
            [x] => 40
            [y] => 22
        )

    [IMG_GENERALIZED_CUBIC] => Array
        (
            [x] => 40
            [y] => 22
        )

    [IMG_HERMITE] => Array
        (
            [x] => 40
            [y] => 22
        )

    [IMG_HAMMING] => Array
        (
            [x] => 40
            [y] => 22
        )

    [IMG_HANNING] => Array
        (
            [x] => 40
            [y] => 22
        )

    [IMG_MITCHELL] => Array
        (
            [x] => 40
            [y] => 22
        )

    [IMG_POWER] => Array
        (
            [x] => 40
            [y] => 22
        )

    [IMG_QUADRATIC] => Array
        (
            [x] => 40
            [y] => 22
        )

    [IMG_SINC] => Array
        (
            [x] => 40
            [y] => 22
        )

    [IMG_NEAREST_NEIGHBOUR] => Array
        (
            [x] => 40
            [y] => 22
        )

    [IMG_WEIGHTED4] => Array
        (
            [x] => 40
            [y] => 22
        )

    [IMG_TRIANGLE] => Array
        (
            [x] => 40
            [y] => 22
        )

)

Notes:
1) On PHP 5.4 it used to be 42 x 23 (it is a test case for Drupal: https://www.drupal.org/node/2215369).
2) The size can even be 2 off, depending on the interpolation setting.
3) I found that positive multiples of 90 degrees work correct, negative multiples are off by 1.

Correction to previous comment: on PHP5.4 it used to be 42 x 24 (and not 42 x 23).

I dove a bit further into the code of both PHP 5.4 and 5.5 and found the following differences:

1) Special cases (i.e multiples of 90 degrees):
- PHP5.4 does normalize angles first to be between 0 and 360 and then checks for equality on 0, 90, 180 and 270
- PHP5.5 does not normalize but checks on angles 0, 90 to 90.01, 180 to 180.01, and 270 to 270.01. The check on not being exactly equal can, considering the imprecision of float arithmetic, be considered a good feature.

2) Computation
- PHP5.4 uses arithmetic that comes down to (PHP syntax and after normalizing to an angle between -45 and +45):
      $rad = deg2rad($degrees);
      $cos = abs(cos($rad)); // always >= 0 for angles between -45 and +45;
      $sin = abs(sin($rad));

      // Shear 1: no intermediate results to store.

      // Shear 2: the width remains the same as after shear 1.
      $newHeight = (int) ($width * $sin + $height * $cos) + 1;

      // Shear 3: the height remains the same as after shear 2, the width is
      // recalculated based on the original dimensions.
      $newWidth =  (int) ($height * $sin + $width * $cos) + 1;

- PHP 5.5 use arithmetic that comes down to (PHP syntax):
        $rad = deg2rad($degrees);
        $cos = cos($rad);
        $sin = sin($rad);

        // This is how GD on PHP5.5 calculates the new dimensions.
        $newWidth = abs((int) ($width * $cos)) + abs((int)($height * $sin + 0.5));
        $newHeight = abs((int) ($width * $sin)) + abs((int)($height * $cos + 0.5));

Errors in PHP 5.5 code:
ad1)
- PHP5.5 misses negative angles like -90, -180 and -270,
- It misses angles just below such a multiple like 89.995.
Why is this a bug?
For reasons of symmetry I would expect both cases to be treated as an 'exact multiple' of 90 degrees and therefore being treated specially.

ad 2)
- PHP5.4 is always rounding up, which is what I would expect. OTOH, PHP5.5 is basically rounding down, though is asymmetrically and only partly compensating for that. It should at least be symmetrical, i.e. the 0.5 should be used in all parts of the calculation.
- The compensation (the + 0.5) is making the situation even worse (i.e. worse than just rounding down) in cases where the (co)sine is negative. So the 0.5 should have the same sign as the accompanying sine or cosine.

Why are these bugs?
For reasons of symmetry I would expect
- The same dimensions if I rotate an image over d or -d degrees.
- The same dimensions for rotating an image of WxH over d degrees and rotating an image of HxW over 90+d degrees, as the latter can be seen as rotating over 90 degrees (swapping W and H) and subsequently rotating over d degrees.
Both symmetries are satisfied by PHP5.4, both aren't by PHP5.5.

Proposal:
- Reintroduce the 'normalization' of the angle to better decide if it is a special case.
- Return to the old PHP 5.4 calculations to compute the new dimensions. I do consider these to be "correct".

The top and left of the image is actually clipped. This problem appears at all rotations: 
<?php
$image = imagecreatetruecolor(500,250);
$bg = imagecolorallocatealpha($image, 255, 255, 127, 127);
$black = imagecolorallocatealpha($image, 0, 0, 0, 0);
$blue = imagecolorallocatealpha($image, 0, 0, 255, 0);
$red = imagecolorallocatealpha($image, 255, 0, 0, 0);
imagesavealpha($image, true);
imagealphablending($image, false);
ImageFill($image, 0, 0 , $bg);
imagerectangle($image,0,0,imagesx($image)-1,imagesy($image)-1,$black);
imagerectangle($image,1,1,imagesx($image)-2,imagesy($image)-2,$blue);
imagerectangle($image,2,2,imagesx($image)-3,imagesy($image)-3,$red);
imagepng($image,'dump1.png');
echo '<img src="dump1.png" /><p>'.(imagesx($image).' x '.imagesy($image)).'</p>';
$image = imagerotate($image,0.1,$bg);
imagepng($image,'dump2.png');
echo '<img src="dump2.png" /><p>'.(imagesx($image).' x '.imagesy($image)).'</p>';
?>

It seems to be only for the default interpolation method, IMG_BILINEAR_FIXED.
Adding:
imagesetinterpolation($image, IMG_BICUBIC);

before calling imagerotate shows the correct result. IMG_BICUBIC_FIXED for example works well too.

I have to check if other are affected but my feeling is that only the bilinear fixed point implementation fails.

If you have time, you can also try it. The various interpolation methods are available here:
http://php.net/manual/en/function.imagesetinterpolation.php

The cause was slightly different. The calculation of the transformed image dimensions were partially wrong.

If you can try this patch, that should fix your issue:

https://gist.github.com/pierrejoye/59d72385ed1888cf8894a7ed437235ae

This has apparently been fixed as of libgd-2.2.2[1], but not yet
been integrated to PHP's bundled libgd.

@pajoye If this issue is considered to be bug, the patch should
probably applied to PHP-5.6+.

[1] <https://github.com/libgd/libgd/commit/6267414d>