Update: Our CAV'04 paper suggests a solution to this problem (see under 'publications' in my web page). This is still not a good solution because it includes an exponential step, while there is no apparent reason for not finding a polynomial approximation.