apri il file .pdf con notepad e vedi con cosa inizia.

di solito ci sono gli header html, probabilmente hai spazi o altro prima dell'output.

se il problema è questo, si può risolvere così;

Codice PHP:
<?php
define
('FPDF_FONTPATH','font/');
require(
'fpdf.php');

$pdf=new FPDF();
$pdf->AddPage();
$pdf->SetFont('Arial','B',16);
$pdf->Cell(40,10,'Hello World!');

ob_end_clean();

$pdf->Output();
?>