I recently submitted a client's web site to a few search engines and happily, it didn't take too long for it to show up at google, etc.
Then, I made a few changes (like page titles) and tried to get the search engines to respider the site again. Unfortunately, this is just not working so far! The "results" still reflect the pages' old titles. I would appreciate any help and advice as to what I am doing wrong, or should be doing. Thanks.
You're not doing anything wrong except not exercisng the patience it takes for the search engines to update. Getting updates in a fairly reasonable amount of time is hit and miss at best. If you've done the necessary changes and resubmitted, then the best thing to do is be patient.