After you got some things synced across, was the iPad still reporting lots of free space? Use, Settings -> General -> About on the iPad itself just to confirm what iTunes is reporting. For example, mine (in iTunes) reports that I have 13.61GB of free space left. But when checking in the device settings, there's actually only 10.7GB of free space, so don't always trust iTunes implicitly.
If there is still lots of free space, try adding the things you removed from your sync a little at a time, it could still be that there's some confusion in the file system reporting. Normally this does sort itself out after a sync or two.