OK, having devoted my lunch hour to this (the sacrifices I make for Physics!) I have an answer for you. I'm not sure this is the best possible answer, so if anyone can improve on it please jump in.
Firstly you're absolutely correct to say that the density of your object increases as it Lorentz contracts. This isn't an illusion: the RHIC observes this every day. Note how the illustrations on the RHIC page I've linked to show the colliding nuclei flattened into disks. However the contracted object can't form a black hole because this violates one of the principles of relativity i.e. the presence or otherwise of the black hole could be used to tell who was moving and who was standing still. So what's going on?
The paradox arises from your assumption that it's the mass/density of the object that determines whether it will be a black hole or not, because this isn't true, or rather it's only true in special cases. The Einstein equation that gives us the curvature, and therefore whether a black hole will form, is:
$$G_{\alpha\beta} = 8\pi T_{\alpha\beta}$$
$G_{\alpha\beta}$ is the Einstein tensor that describes the curvature, while $T_{\alpha\beta}$ is the stress-energy tensor. So it's not the mass/density of the object that determines the curvature, it's the stress-energy tensor.
There's a shortcut here, because the stress-energy tensor is an invarient i.e. it is the same in all co-ordinate systems. That means the stress-energy tensor we observe is the same as the stress-energy tensor observed in the rest frame of your test object. So if the test object doesn't form a black hole in it's rest frame it will not form a black hole in any other co-ordinate system, even the one you describe in which the object is moving at almost the speed of light.
However it's at this point that I run out of steam a bit, which is why I think there's scope for this answer to be improved. It would be nice to give an intuitive feel for what the stress-energy tensor is, and why it doesn't change when we see the object moving at almost the speed of light. We normally write the stress-energy tensor as a 4 x 4 matrix, and with a few approximations about your test object the tensor only has one non-zero value, $T_{00}$, which is indeed the density. If we write the stress-energy tensor in our frame, where the object is moving, our value for $T_{00}$ will increase as the density increases, and if nothing else changed this would eventually form a black hole. However in our frame the other entries in the matrix are no longer zero. The changes in the other entries balance out the change in the density, so when we plug our stress-energy tensor into the Einstein equation we get the same curvature as in the test object's rest frame. No black hole!