What do you mean by your site map? Do you mean the sitemap XML file that gets uploaded to Google Webmaster Tools, or your site's navigation menu? Any time that you change your site navigation, it takes time for Google to catch on and recrawl your entire site. Changing the XML file should not really make much of a difference.
Browsing your site, I can make the following recommendations:
Aside from the homepage being the top two most recent items, put a bulleted list of the top ten most recent items with links to them. This will bring in some more deep links from the site homepage.
I see that you have links to your Twitter page, Facebook page, etc. at the top right sidebar of every page. That's a good start, but it's also a good idea to put the widgets to "Tweet this Page" or "Share this Page with your FB Friends". You want to focus on increasing the number of backlinks to interior pages of your site.
Remember, Google's algorithm is changing every day, so you need to work just as hard to keep up with it :)