Here is code to parse and decode all types of messages, including attachments. I've been using something like this for a while now, so it's pretty robust.

<?php
function getmsg($mbox, $mid) {
    // input $mbox = IMAP stream, $mid = message id
    // output all the following:
    global $charset, $htmlmsg, $plainmsg, $attachments;
    $htmlmsg = $plainmsg = $charset = '';
    $attachments = array();

    // HEADER
    $h = imap_header($mbox, $mid);
    // add code here to get date, from, to, cc, subject...

    // BODY
    $s = imap_fetchstructure($mbox, $mid);
    if (!$s->parts)  // simple
        getpart($mbox, $mid, $s, 0);  // pass 0 as part-number
    else {  // multipart: cycle through each part
        foreach ($s->parts as $partno0=>$p)
            getpart($mbox, $mid, $p, $partno0+1);
    }
}

function getpart($mbox, $mid, $p, $partno) {
    // $partno = '1', '2', '2.1', '2.1.3', etc for multipart, 0 if simple
    global $htmlmsg, $plainmsg, $charset, $attachments;

    // DECODE DATA
    $data = ($partno)?
        imap_fetchbody($mbox,$mid,$partno):  // multipart
        imap_body($mbox,$mid);  // simple
    // Any part may be encoded, even plain text messages, so check everything.
    if ($p->encoding==4)
        $data = quoted_printable_decode($data);
    elseif ($p->encoding==3)
        $data = base64_decode($data);

    // PARAMETERS
    // get all parameters, like charset, filenames of attachments, etc.
    $params = array();
    if ($p->parameters)
        foreach ($p->parameters as $x)
            $params[strtolower($x->attribute)] = $x->value;
    if ($p->dparameters)
        foreach ($p->dparameters as $x)
            $params[strtolower($x->attribute)] = $x->value;

    // ATTACHMENT
    // Any part with a filename is an attachment,
    // so an attached text file (type 0) is not mistaken as the message.
    if ($params['filename'] || $params['name']) {
        // filename may be given as 'Filename' or 'Name' or both
        $filename = ($params['filename'])? $params['filename'] :
$params['name'];
        // filename may be encoded, so see imap_mime_header_decode()
        $attachments[$filename] = $data;  // this is a problem if two files have same name
    }

    // TEXT
    if ($p->type==0 && $data) {
        // Messages may be split in different parts because of inline
attachments,
        // so append parts together with blank row.
        if (strtolower($p->subtype)=='plain')
            $plainmsg .= trim($data) ."\n\n";
        else
            $htmlmsg .= $data ."<br><br>";
        $charset = $params['charset'];  // assume all parts are same charset
    }

    // EMBEDDED MESSAGE
    // Many bounce notifications embed the original message as type 2,
    // but AOL uses type 1 (multipart), which is not handled here.
    // There are no PHP functions to parse embedded messages,
    // so this just appends the raw source to the main message.
    elseif ($p->type==2 && $data) {
        $plainmsg .= $data."\n\n";
    }

    // SUBPART RECURSION
    if ($p->parts) {
        foreach ($p->parts as $partno0=>$p2)
            getpart($mbox, $mid, $p2, $partno.'.'.($partno0+1));  // 1.2, 1.2.1, etc.
    }
}
?>

Assuming $struct = imap_fetchstructure($x,$y);

It is important to note that if a message has NO attachements, $struct->parts is an empty array, and $struct->bytes has a value.  If a message as ANY attachements, $struct->bytes ALWAYS = 0. To get the size of the primary body, you have to call structure->part[0]->bytes.  To get the size of the whole message, either strlen(imap_body) or add up the ->bytes of all the parts.

Another interesting note: 
When there is body text and no attachements:
count($struct->parts) = 0
When there is body text and 1 attachement:
count($struct->parts) = 2

These imap functions could really use better documentation. Like giving the meathods for the dparameter and parameter classes...

Point of clarification:

The seventh primary body type is not "Other" as documented, but actually "Model".  This encompasses IGES, VRML, MESH, DWF, etc.

http://www.isi.edu/in-notes/iana/assignments/media-types/media-types

"Other" is the eigth primary body type.

For people just beging this may help alot as I spent a couple hours just trying to relize how exact the array was stored. (at the time I did not know the print_r function :P)

$struct = imap_fetchstructure($mbox, $msgnumber);
print_r($struct);

Will give you a better example for your messages but they are called as $struct using the varible method above.

$struct->type; //would return the type
$struct->encoding //would return the encoding 

and etc..

This can be done many different ways but that is the basics on pulling the info out of the structure of fetchstructure itself, I hope it helps someone starting because it wouldve helped me :/.

"Primary body type" of "unknown/unknown" will be int(9).

I think the following line (when building attachment information)

>>> "filename" => $parts[$i]->parameters[0]->value

needs to be

>>> "filename" => $parts[$i]->dparameters[0]->value

The first version generated a PHP warning under PHP 5.0.3.  The second version actually gets the filename.

Another comment to inform people about something that should really be in the function description:

imap_fetchstructure() downloads the entire email, attachments and all, rather than just the structure.
I guess it's an undocumented feature, not a bug.

I had assumed that the script would have only downloaded the amount of data that was returned, but my script downloaded a cumulative 2.5gig before i noticed.  Hopefully no-one else will have this happen.

If you have errors with wrong attachment names like this:

correct name:
String -> Prüfbericht Hersteller.pdf

fetchstructure object name:
 =?ISO-8859-1?Q?Pr=FCfbericht_Hersteller=2Epdf?=

Workaround to reconvert:

imap_mime_header_decode($fetchstructure->dparameters->value)[0]->text

imap_mime_header_decode($filename)[0]->text

If you logic based on compare structure strings, you must compare it case insensetive.
<?php

$p = imap_fetchstructure($this->_imap_resource, $mid);
//do not compare $p->disposition == 'INLINE' 
if(preg_match('/inline/i', $p->disposition)) 
{
 //this works
}
?>

An update on the note from david at hundsness dot com ¶. I have used his contribution with great success, just a couple of issues. The syntax used for some string concatenations was in the form $var. = $var2, but should be $var .= $var2. I also had to add some checks for the existence of some properties, especially the structure dparameters and the keys filename and name in the parameters property. But the code has been a huge help.