I have a large document with an index compiled through makeindex, and is included in my source .tex as follows:

\cleardoublepage
\phantomsection
\printindex

Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . 330

One solution is to write a new command, \immediateaddcontentsline, and this adds the Index to both the TOC and the list of Bookmarks. The Bookmark link works correctly. But in the TOC, the page number is now listed with roman numerals as "xvi" rather than "349".

Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . 330

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi

"xvi" is the current page, so it looks like something is mighty confused. It is probably related to the immediate-ness of the new TOC command.

Is it even possible to have an Index listed the Table of Contents? Or must I use a different index maker?

-
Which document class are you using? The KOMA classes, for example, provide an option to include the index in the table of contents (and the Memoir classes might have a similar option). As we cannot guess what you did with your \immediateaddcontentsline command, please add a minimal working example (MWE) that illustrates your problem. –  domwass Oct 14 '11 at 7:30
Could the tocbibind package be of help? Edit: If you're using KOMA rather use domwass' suggestion, tocbibind is made to work with the standard classes. –  Torbjørn T. Oct 14 '11 at 7:30

Instead of tinkering with \addcontentsline, simply load my idxlayout package with the totoc option. (idxlayout is compatible with the standard classes, the KOMA-Script classes, and memoir.)

\documentclass{report}

\usepackage{makeidx}
\makeindex

\usepackage[totoc]{idxlayout}

\usepackage{hyperref}

\begin{document}

\tableofcontents

\chapter{foo}

Some text.\index{Text}

\printindex

\end{document}
-

assuming that \printindex triggers \chapter* and chapters always start on right-hand pages, try inserting \cleardoublepage and then the \addcontentsline. if a chapter can start on either a right-hand or a left-hand page, \clearpage should suffice.

-

\usepackage[nottoc,notbib]{tocbibind}

and place a \phantomsection before the index, so that the hyperlink does not aim at some content before the index.

-
tocbibind produces right page number in toc, but it links Index to the previous chapter. –  Anton Petrunin Feb 7 '13 at 19:04
@AntonPetrunin: What happens when you place a \phantomsection before the index? –  Stephen Feb 7 '13 at 20:06
yes it works, thank you. –  Anton Petrunin Feb 10 '13 at 4:14

Reversing the order of the lines might do the trick, e.g.,

\printindex