Hi Unikron,
Well a tiny update on what is going on. We have been redoing all our graphics and now we have a game resolution of 640x960. Whilst I can't say if the problem has occured or gone away, I am thinking it could be to do with pixel aspect ratio after all.
What I have done is coded the game so a single Unity world coordinate is the same as 1 pixel. Therefore the game runs in 640x960 Unity world coordinates so it should be pixel perfect aspect ratio when rendered on a mobile device.
Whilst everything looks ok in the GUI, once I compile to certain devices the pixels are slightly blurry, same sort of issues I was having before. When sprites move across there is a clear pixel twitching effect.
I have ticked the boxes in tk2d for pixel perfect. Have messed with the camera, I even attached your Tk2d pixel perfect helper script into the camera and messed around with the settings in that, and nothing seems to make any difference. Very odd indeed.
I still can't work out whether this is a fault in Unity, your library, or some mistake that I have missed.
The particle system is using Unity's inbuilt particle system instead of your library since it was faster, but these particles all look fine and have no problems with pixelation at all.
The plot thickens.