Ok the problem was that I never actually applied the rigidbody properly. Thanks for the help!

Is the Sphere that this script is on also a trigger?

edit: actually the example code for C# does have some stuff not present in your script.

using UnityEngine;
using System.Collections;

public class example : MonoBehaviour {
    void OnTriggerEnter(Collider other) {
        Destroy(other.gameObject);
    }
}

I'm not a C# user myself but it might just need those first few extra lines and also the "public class example" part before it will work at all.

No but I tried that and it doesn't change anything.

Ok I went ahead and replicated the scene you described, and it seems to be working fine. This is what the entire script I have looks like:

using UnityEngine;
using System.Collections;

public class test2 : MonoBehaviour {

    public GameObject ParticlePrefab;

    void OnTriggerEnter(Collider col){
       Debug.Log("Hit");
       Destroy(col.gameObject);
       //Instantiate(ParticlePrefab, transform.position, transform.rotation);
    }
}

Though as you can see I commented out the Instantiate part, the Debug.Log part is definitely working. So I'm not sure what's going on with yours.. my scene is using a simple Unity sphere and capsule, the sphere has the script on it, and the capsule has a rigidbody applied and nothing else. Are you using a character controller on your capsule?