I have run into this before, I was using headway for a theme and the cause of the problem was a conflict with other plug-ins & a needed upgrade to my theme.
Troubleshooting:
Disable all other plug ins and try it again.
if it works enable your plug ins one at a time and see which one is in conflict.
If there is no change, make sure you are using the latest WP, Theme version, and NextGEN version. Upgrade as needed.
re-check your settings, and your PHP version as well.
On the gallery overview page run the plug in check.
if that does not work post the details of your set up here –
use the information in the block on the gallery overview page like so:
Operating System : Linux (64 Bit)
Server : Apache/2.2.23 (Unix) mod_ssl/2.2.23 OpenSSL/0.9.8e-fips-rhel5
Memory usage : 29.39 MByte
MYSQL Version : 5.0.96-community
SQL Mode : Not set
PHP Version : 5.3.18
PHP Safe Mode : Off
PHP Allow URL fopen : On
PHP Memory Limit : 64
PHP Max Upload Size : 10M
PHP Max Post Size : 8M
PCRE Backtracking Limit : 500000
PHP Max Script Execute Time : 10s
PHP Exif support : No
PHP IPTC support : Yes
PHP XML support : Yes
Graphic Library
GD Version : bundled (2.0.34 compatible)
FreeType Support : Yes
FreeType Linkage : with freetype
T1Lib Support : No
GIF Read Support : Yes
GIF Create Support : Yes
JPEG Support : Yes
PNG Support : Yes
WBMP Support : Yes
XPM Support : Yes
XBM Support : Yes
JIS-mapped Japanese Font Support : No
mine works and has those settings.