David,
If Jim and I finish our work for 8.1, then you'll be able to do:
SELECT approx_records FROM pg_sysviews.pg_tables WHERE schema_name = 'schema'
AND table_name = 'table'
But the same caveats will apply.
--
Josh Berkus
Aglio Database Solutions
San Francisco