How to publish new results for a paper under review?
There are three basic routes that you can take for close incremental improvements of this sort, depending on timing and the complexity of the work to be described.  They are:


If the improvement is relatively simple (could be fit into the existing paper), and is completed before the camera-ready deadline of the conference, then the best thing to do is to incorporate it into the current paper when you revise for the camera-ready version.  This type of improvement is generally acceptable in conference publications.
If the improvement is complex and impactful enough to deserve its own paper, write that paper and reference the current paper as "submitted."  If both are accepted, then the timing is likely to be such that you can change the citation to the final venue and date for the camera-ready of the second paper.
If the improvement is both too late for the current camera-ready and too small for its own paper, you can either incorporate it into an extended version of the original paper to be sent to a journal (I've done this several times myself) or else can post a brief technical note in a non-peer-reviewed but respectable and archival venue (e.g., arXiv, a tech report at your institution).


For your particular case, it sounds like option #1 (incorporate into the camera-ready) is likely to apply, but #3 may also be a reasonable path.