As near as I can tell the program is technically working correctly. Instead your visual artifacts stem from the limited 8-bit fixed-point precision in the affine transformation used by the hardware.
Essentially the difference between a 0 and 1 in the sine tables makes a rather large and visible jump in the rotation for the right-angles in your rectangular sprite, while the 0°/90°/180°/270° corners are not that special for the round earth background.
The tangent for the (co-)sine function at 0 is high, so if you look at your tables there is only a single spot where they are precisely 0. If the rotation doesn't fall precisely on this index the result looks visibly skewed.
What you may try however is to cheat by fiddling with the rounding to produce more consecutive zeroes. At the moment you table generator is scaling by 256 and rounding towards the nearest integer:
sine[i] = floor(sin(i * M_PI / 1024.0) * 256.0 + 0.5);
As an alternative we may skew the table a little by rounding towards zero, as is the default in C, and increasing the scale to insure that the table still reaches 256 for at more than one entry.
int value = sin(i * M_PI / 1024.0) * 257.0;
if(value < -256) value = -256;
if(value > +256) value = +256;
sine[i] = value;
The table may be then flattened even further by increasing the scaling factor even further.
The problem is also that for small sprites near right angles there is nowhere for the rotation to go.
Picture a 64x1 straight line sprite pointing vertically at nearly an almost straight angle, with only the minimum 1/256th fractional step from the sine table. Keep in mind that the rotation is always centered so you get one jagged horizontal step precisely at the center.
For each of the 32 pixels from the center outwards you then add up another 1/256th fraction to the texture coordinate. However all of these together only make for 1/8th of a pixel in total and so no more horizontal steps are taken. In fact for this sprite shape you will see no visible change until the rotation angle reaches a full 8/256th fraction.
On the other hand your large earth object is sufficiently big to always show multiple visible integer "steps." This means that an increased rotation angle will always at least shift the position of the non-centered step, even if it insufficient to add up to another full pixel along entire side. The result is a smoother overall effect due to the continual animation.