There are a few things you can do to improve the accelerometer accuracy.

Install a compass app from Market, many have a calibration feature that helps with the compass accuracy, but also helps in general. The procedure usually involves moving the device in a figure 8, laying it down on a flat surface and rotating it, etc, very similar to what you say you've tried, but with specific directions.

Try that and see if it helps.