<p>I've got 256 colors working great in my terminal (<a href="http://www.frexx.de/xterm-256-notes/" rel="noreferrer">test scripts here</a>), but it stops working when I use ncurses (via Ruby-ncurses). Printing the escape sequences given on that page works fine, but when I initialize ncurses 'puts' stops working and I can't output the colors with any of the various ncurses color changing/string output functions I've found. What gives?</p>

I am not sure if this would be all the story, but make sure your terminal capabilities do indeed provide for the 256 colors description.
What is the TERM environment variable value? Try setting it to xterm-256color and rerun it.
ncurses should then get the proper color escape sequences.
You can also test the terminal capabilities and terminal color output with the program we use at SXEmacs development:
http://www.triatlantico.org/tmp/tty-colors.c
Compile with gcc -o tty-colors tty-colors.c -lncurses
EDIT:
Note that just because the scripts that are found on the net output the 256 colors, that is not "all set".
Curses programs rely on terminfo and termcap and the TERM environment variable to find out how to interact with the terminal.
So in order for a curses app to be able to use the 256 colors one should set the TERM variable to an existing terminal name which supports 256 colors.
The C program above will show you
what
ncurses thinks about your terminal, not just output the xterm sequences like most scripts do [even the one from X.org]