fill-paragraph does not honor fill-column

Filling is a general facility which can depend on more than just the fill-column variable, however the first thing to test is simply that you're checking the fill-column value for the correct buffer -- it can have a different value in each buffer; so if you typed C-hv from some other buffer, you might see the wrong value.

C-hf fill-paragraph tells us that its behaviour depends on the value of the fill-paragraph-function variable, which in turn is described thus:

Mode-specific function to fill a paragraph, or nil if there is none. If the function returns nil, then `fill-paragraph' does its normal work. A value of t means explicitly "do nothing special". Note: This only affects `fill-paragraph' and not `fill-region' nor `auto-fill-mode', so it is often better to use some other hook, such as `fill-forward-paragraph-function'. 

In *scratch* C-hv fill-paragraph-function leads us to:

lisp-fill-paragraph is an interactive compiled Lisp function in `lisp-mode.el'. (lisp-fill-paragraph &optional JUSTIFY) Like M-q, but handle Emacs Lisp comments and docstrings. If any of the current line is a comment, fill the comment or the paragraph of it that point is in, preserving the comment's indentation and initial semicolons. 

Similarly, in c-mode buffers we're using the function c-fill-paragraph (which see).

As you might imagine, many of the mode-specific functions use alternative variables with fill-column in their name, so this ought to show you some illuminating things as well:

M-x apropos-variable RET fill-column RET