I saw your site, and the 404 page. It does use apache. Was your SEO friendly URLs working before, or did this start happening when you installed it?
EDIT: It looks like your using the default MyBB .htaccess, but are using the Google SEO plugin, am i correct?
Replace your .htaccess with
# EXAMPLE .htaccess FOR MYBB WITH GOOGLE SEO URL
# -------------------------------------------------------------------
# This file is identical to MyBB's htaccess.txt example file,
# with rewrite rules for a standard Google SEO install added.
#
# Before using this file please make sure to:
#
# - replace /MyBB/ with your forum folder, e.g. / or /forum/
# - replace yoursite/MyBB with your forum URL
# - name the file '.htaccess' (starting with the dot, no .txt)
#
# Alternatively you can add the required rewrite rules to your
# existing .htaccess, the specific rules required will be displayed
# on the plugin status page once Google SEO URL is enabled.
# -------------------------------------------------------------------
Options -MultiViews +FollowSymlinks -Indexes
#
# If mod_security is enabled, attempt to disable it.
# - Note, this will work on the majority of hosts but on
# MediaTemple, it is known to cause random Internal Server
# errors. For MediaTemple, please remove the block below
#
<IfModule mod_security.c>
# Turn off mod_security filtering.
SecFilterEngine Off
# The below probably isn't needed, but better safe than sorry.
SecFilterScanPOST Off
</IfModule>
#
# MyBB "search engine friendly" URL rewrites
# - Note, for these to work with MyBB please make sure you have
# the setting enabled in the Admin CP and you have this file
# named .htaccess
#
<IfModule mod_rewrite.c>
RewriteEngine on
# Some hosts need a RewriteBase specification.
RewriteBase /
# Google SEO workaround for search.php highlights:
# Make this rule the first rewrite rule in your .htaccess!
RewriteRule ^([^&]*)&(.*)$ http://bamanation.net/$1?$2 [L,QSA,R=301]
# Google SEO Sitemap:
RewriteRule ^sitemap-([^./]+)\.xml$ misc.php?google_seo_sitemap=$1 [L,QSA,NC]
# Google SEO URL Forums:
RewriteRule ^Forum-([^./]+)$ forumdisplay.php?google_seo_forum=$1 [L,QSA,NC]
# Google SEO URL Threads:
RewriteRule ^Thread-([^./]+)$ showthread.php?google_seo_thread=$1 [L,QSA,NC]
# Google SEO URL Announcements:
RewriteRule ^Announcement-([^./]+)$ announcements.php?google_seo_announcement=$1 [L,QSA,NC]
# Google SEO URL Users:
RewriteRule ^User-([^./]+)$ member.php?action=profile&google_seo_user=$1 [L,QSA,NC]
# Google SEO URL Calendars:
RewriteRule ^Calendar-([^./]+)$ calendar.php?google_seo_calendar=$1 [L,QSA,NC]
# Google SEO URL Events:
RewriteRule ^Event-([^./]+)$ calendar.php?action=event&google_seo_event=$1 [L,QSA,NC]
# Google SEO 404:
ErrorDocument 404 /misc.php?google_seo_error=404
# Default MyBB Rewrite Rules:
RewriteRule ^forum-([0-9]+)\.html$ forumdisplay.php?fid=$1 [L,QSA]
RewriteRule ^forum-([0-9]+)-page-([0-9]+)\.html$ forumdisplay.php?fid=$1&page=$2 [L,QSA]
RewriteRule ^thread-([0-9]+)\.html$ showthread.php?tid=$1 [L,QSA]
RewriteRule ^thread-([0-9]+)-page-([0-9]+)\.html$ showthread.php?tid=$1&page=$2 [L,QSA]
RewriteRule ^thread-([0-9]+)-lastpost\.html$ showthread.php?tid=$1&action=lastpost [L,QSA]
RewriteRule ^thread-([0-9]+)-nextnewest\.html$ showthread.php?tid=$1&action=nextnewest [L,QSA]
RewriteRule ^thread-([0-9]+)-nextoldest\.html$ showthread.php?tid=$1&action=nextoldest [L,QSA]
RewriteRule ^thread-([0-9]+)-newpost\.html$ showthread.php?tid=$1&action=newpost [L,QSA]
RewriteRule ^thread-([0-9]+)-post-([0-9]+)\.html$ showthread.php?tid=$1&pid=$2 [L,QSA]
RewriteRule ^post-([0-9]+)\.html$ showthread.php?pid=$1 [L,QSA]
RewriteRule ^announcement-([0-9]+)\.html$ announcements.php?aid=$1 [L,QSA]
RewriteRule ^user-([0-9]+)\.html$ member.php?action=profile&uid=$1 [L,QSA]
RewriteRule ^calendar-([0-9]+)\.html$ calendar.php?calendar=$1 [L,QSA]
RewriteRule ^calendar-([0-9]+)-year-([0-9]+)\.html$ calendar.php?action=yearview&calendar=$1&year=$2 [L,QSA]
RewriteRule ^calendar-([0-9]+)-year-([0-9]+)-month-([0-9]+)\.html$ calendar.php?calendar=$1&year=$2&month=$3 [L,QSA]
RewriteRule ^calendar-([0-9]+)-year-([0-9]+)-month-([0-9]+)-day-([0-9]+)\.html$ calendar.php?action=dayview&calendar=$1&year=$2&month=$3&day=$4 [L,QSA]
RewriteRule ^calendar-([0-9]+)-week-(n?[0-9]+)\.html$ calendar.php?action=weekview&calendar=$1&week=$2 [L,QSA]
RewriteRule ^event-([0-9]+)\.html$ calendar.php?action=event&eid=$1 [L,QSA]
<IfModule mod_env.c>
SetEnv SEO_SUPPORT 1
</IfModule>
</IfModule>
#
# If Apache is compiled with built in mod_deflade/GZIP support
# then GZIP Javascript, CSS, HTML and XML so they're sent to
# the client faster.
#
<IfModule mod_deflate.c>
AddOutputFilterByType DEFLATE application/x-javascript text/css text/html text/xml
</IfModule>
