"Low on space" message on an android tablet
Even if you move apps to the SDcard, the apps will still use space in /data/data/ this is where the user data is stored for the application. this includes things like the database, additional application specific files, other cached data. 

Devices that do not have large a /data/data partition are very troublesome with a lot of current applications. Applications like Google+, Chrome, Gmail (just as a couple examples) can use a lot of space in /data/data/.

To see if the issue is /data/data/ you can try and clear Data for some applications and see if the notification goes away. Not just the cache for the application, actually clearing the data.